当前数组 a1 a2 a3.....an;
对于每个下表i，求 aj<ai ( j<i ) 的个数,为当ai的文化素养，
点击查看代码
#include<bits/stdc++.h>
using namespace std;
const int N=1e7+9;
int e[N],a[N],lazy[N];
void buidtree(int k,int l,int r)
{
if(l==r)
{
e[k]=0;
return ;
}
int mid=(l+r)>>1;
buidtree(k<<1,l,mid);
buidtree(k<<1|1,mid+1,r);
e[k]=e[k<<1]+e[k<<1|1];
return ;
}
void push(int k,int l,int r,int w)
{
if(l==r)
{
// cout<<l<<endl;
e[k]++;
return ;
}
int mid=(l+r)>>1;
if(mid<w)
{
push(k<<1|1,mid+1,r,w);
}
else push(k<<1,l,mid,w);
e[k]=e[k<<1]+e[k<<1|1];
return ;
}
int cha(int k,int l,int r,int x,int y)
{
if(x<=l&&y>=r)
{
return e[k];
}
int mid=(l+r)>>1;
int ans=0;
if(mid>=x)
{
ans+=cha(k<<1,l,mid,x,y);
}
if(y>mid)
{
ans+=cha(k<<1|1,mid+1,r,x,y);
}
return ans;
}
//void pushdown(int k)
//{
// e[k<<1]
//}
struct node
{
int x,y;
}p[N];
bool cam(node x,node y)
{
if(x.x!=y.x)
return x.x<y.x;
return x.y>y.y;
}
int main()
{
int n,d;
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>d;
p[i].x=d;
p[i].y=i;
}
buidtree(1,1,n);
sort(p+1,p+1+n,cam);
for(int i=1;i<=n;i++)
{
int x=p[i].y;
int y=p[i].x;
// cout<<y<<" "<<x<<endl;
y=cha(1,1,n,1,x);
push(1,1,n,x);
// cout<<y<<endl;
a[x]=y;
}
for(int i=1;i<=n;i++)
{
cout<<a[i]<<" ";
}
return 0;
}