题解 P3157 【[CQOI2011]动态逆序对】
我知道这题有很多题解了 但是我看了很久也没看明白 自己调了半天才过
首先这道题我们要维护一个数列 支持查询一个数之前有多少比他大的和他之后有多少比他小的 以及删除一个数
如果没有删除 我们可以用主席树来维护 从每颗主席树的root[i]进去可以访问到区间为1-i的权值线段树。这相当于维护1-i的前缀和。类比序列 如果我们加上了删除操作 我们就需要用树状数组来维护了 树状数组中i维护了i-lowbit(i)到i的和。那么在这道题中 从root[i]进去就应该访问到区间为i-lowbit(i)到i的权值线段树 这样的话 删除和询问就可以2个log做出来了
另外这题空间很玄学 按照上面的算法 每个点存log遍 存一遍要log个点 空间复杂度是nlog^2n 就MLE了 但是刚才那么算明显多算了一些 实际上 数组开1000w就行了
#include<iostream>
using namespace std;
int ls[10000010],rs[10000010],cnt[10000010],n,a[100010],q,root[100010],b[100010],shu[100010],num;
long long ans;
int lowbit(int x)
{
return x&(-x);
}
void add0(int x,int v)
{
while(x<=n)
{
shu[x]+=v;
x+=lowbit(x);
}
}
long long sum0(int x)
{
long long s0=0;
while(x>0)
{
s0+=shu[x];
x-=lowbit(x);
}
return s0;
}
int query0(int x,int y)
{
return sum0(y)-sum0(x-1);
}
void update(int l,int r,int &now,int val)
{
if(now==0) now=++num;
cnt[now]++;
if(l==r) return;
int m=(l+r)/2;
if(val<=m) update(l,m,ls[now],val);
else update(m+1,r,rs[now],val);
}
int countda(int l,int r,int now,int v)
{
//cout<<l<<" "<<r<<" "<<now<<" "<<v<<" "<<rs[now]<<" "<<cnt[rs[now]]<<endl;
if(now==0)return 0;
if(l==r)
if(v<l) return cnt[now];
else return 0;
int m=(l+r)/2;
if(v>m) return countda(m+1,r,rs[now],v);
return cnt[rs[now]]+countda(l,m,ls[now],v);
}
int queryda(int x,int y,int v)
{
if(x>y) return 0;
int tt=0;
x--;
while(y>0)
{
tt+=countda(1,n,root[y],v);
y-=lowbit(y);
}
while(x>0)
{
tt-=countda(1,n,root[x],v);
x-=lowbit(x);
}
return tt;
}
int countxiao(int l,int r,int now,int v)
{
if(now==0) return 0;
//if(v==1) cout<<l<<" "<<r<<" "<<now<<" "<<v<<endl;
if(l==r)
if(v>l) return cnt[now];
else return 0;
int m=(l+r)/2;
if(v<=m) return countxiao(l,m,ls[now],v);
return cnt[ls[now]]+countxiao(m+1,r,rs[now],v);
}
int queryxiao(int x,int y,int v)
{
if(x>y) return 0;
int tt=0;
x--;
while(y>0)
{
tt+=countxiao(1,n,root[y],v);
y-=lowbit(y);
}
while(x>0)
{
tt-=countxiao(1,n,root[x],v);
x-=lowbit(x);
}
return tt;
}
void del(int l,int r,int now,int v)
{
if(now==0) return;
cnt[now]--;
if(l==r) return;
int m=(l+r)/2;
if(v<=m) del(l,m,ls[now],v);
else del(m+1,r,rs[now],v);
}
void shanchu(int x,int v)
{
while(x<=n)
{
del(1,n,root[x],v);
x+=lowbit(x);
}
}
int main()
{
int i,t0,j;
cin>>n>>q;
for(i=1;i<=n;i++)
{
cin>>a[i];
ans+=query0(a[i]+1,n);//求初始逆序对
add0(a[i],1);
b[a[i]]=i;
for(j=i-lowbit(i)+1;j<=i;j++) update(1,n,root[i],a[j]);//插入
}
for(i=1;i<=q;i++)
{
cin>>t0;
cout<<ans<<endl;
ans-=(long long)queryda(1,b[t0]-1,t0)+queryxiao(b[t0]+1,n,t0);//计算
shanchu(b[t0],t0);//删除
}
system("pause");
return 0;
}