#include<stdio.h> #include<iostream> #include<map> #include<string.h> #include<algorithm> #include<math.h> #include<vector> #define ll long long using namespace std; const int maxn=100005; int a[maxn]; ///记录原始数据 int ans[maxn]; ///记录答案 int b[maxn]; ///这是一个01序列，某一个位置p上的位置为1，代表着a[p]这个数字最后出现的位置是p，而a[p]曾经出现的位置上都是0 int n; map<int,int>LastIndex; struct tree { int l,r; ///l,r左右端点 int sum; ///sum区间和 } t[maxn*4]; void build(int p, int l, int r) { ///当前的节点，左子节点，右子节点 t[p].l=l; t[p].r=r; if(l==r) ///根节点 { t[p].sum=a[r]; return ; ///从下往上传数据 } int mid=(l+r)>>1; /// build(p*2,l,mid);///建左子树 build(p*2+1,mid+1,r); ///建右子树 t[p].sum=t[p*2].sum+t[p*2+1].sum; } void change(int p,int x,int v)//单点修改 { if(t[p].l==t[p].r) { t[p].sum=v; return ; } int mid=(t[p].l+t[p].r)>>1; if(x<=mid) change(p*2,x,v); else change(p*2+1,x,v); t[p].sum=t[p*2].sum+t[p*2+1].sum; } int ask(int p,int x,int y) { int l=t[p].l; int r=t[p].r; if(x<=l&&y>=r) { return t[p].sum; } int mid=(l+r)/2; int ans=0; if(x<=mid) { ans+=ask(p*2,x,y); } if(y>mid) { ans+=ask(p*2+1,x,y); } return ans; } int main() { LastIndex.clear(); scanf("%d",&n); for(int i=1;i<=n;i++) { scanf("%d",&a[i]); } build(1,1,n); for(int i=1;i<=n;i++) { int num=a[i]; int preIndex=LastIndex[num]; if(preIndex==0) { ans[i]=-num; b[i]=1; change(1,i,1); } else { ans[i]=ask(1,preIndex+1,i-1); ///统计两个位置之间的1的个数 ，其实就是求区间和 b[i]=1; b[preIndex]=0; change(1,i,1); change(1,preIndex,0); } LastIndex[num]=i; ///更新 } for(int i=1;i<=n;i++) { printf("%d",ans[i]); if(i!=n) printf(" "); } printf("\n"); }
