题解 P3157 【[CQOI2011]动态逆序对】
zcysky
2017-06-17 10:42:22
其实我是想练CDQ分治的……结果忍不住又写了个主席树。
首先看看不动态的逆序对咋做？树状数组嘛。
那么删除咋搞？就是考虑贡献，把它前面比他大的，后面比他小的减去……
所以就是一个带修改的主席树啦。
带修改主席树很套路的吧。
不会这个东西的可以去做dynamic rankinga
我在这里就简单说一下吧
普通主席树差分实现
带修改的话主席树维护形态，树状数组维护前缀和。
好了，没了。
所以这题就很简单了。
```cpp
#include<bits/stdc++.h>
#define inf 0x7fffffff
#define N 100005
#define M 5000005
using namespace std;
typedef long long ll;
ll ans;
int n,m,sz,a[100],b[100],val[N],pos[N],a1[N],a2[N];
int c[N*10],rt[N],ls[M],rs[M],sumv[M];
inline int lowbit(int x){return x&(-x);}
inline int ask(int x){
int ans=0;
for(int i=x;i;i-=lowbit(i))ans+=c[i];
return ans;
}
void change(int &o,int l,int r,int q){
if(!o)o=++sz;sumv[o]++;
if(l==r)return;
int mid=(l+r)>>1;
if(q<=mid)change(ls[o],l,mid,q);
else change(rs[o],mid+1,r,q);
}
int querysub(int x,int y,int v){
int cnta=0,cntb=0;int ans=0;x--;
for(int i=x;i;i-=lowbit(i))a[++cnta]=rt[i];
for(int i=y;i;i-=lowbit(i))b[++cntb]=rt[i];
int l=1,r=n;
while(l!=r){
int mid=(l+r)>>1;
if(v<=mid){
for(int i=1;i<=cnta;i++)ans-=sumv[rs[a[i]]];
for(int i=1;i<=cntb;i++)ans+=sumv[rs[b[i]]];
for(int i=1;i<=cnta;i++)a[i]=ls[a[i]];
for(int i=1;i<=cntb;i++)b[i]=ls[b[i]];
r=mid;
}
else{
for(int i=1;i<=cnta;i++)a[i]=rs[a[i]];
for(int i=1;i<=cntb;i++)b[i]=rs[b[i]];
l=mid+1;
}
}
return ans;
}
int querypre(int x,int y,int v){
int cnta=0,cntb=0,ans=0;x--;
for(int i=x;i;i-=lowbit(i))a[++cnta]=rt[i];
for(int i=y;i;i-=lowbit(i))b[++cntb]=rt[i];
int l=1,r=n;
while(l!=r){
int mid=(l+r)>>1;
if(v>mid){
for(int i=1;i<=cnta;i++)ans-=sumv[ls[a[i]]];
for(int i=1;i<=cntb;i++)ans+=sumv[ls[b[i]]];
for(int i=1;i<=cnta;i++)a[i]=rs[a[i]];
for(int i=1;i<=cntb;i++)b[i]=rs[b[i]];
l=mid+1;
}
else{
for(int i=1;i<=cnta;i++)a[i]=ls[a[i]];
for(int i=1;i<=cntb;i++)b[i]=ls[b[i]];
r=mid;
}
}
return ans;
}
inline int read(){
int f=1,x=0;char ch;
do{ch=getchar();if(ch=='-')f=-1;}while(ch<'0'||ch>'9');
do{x=x*10+ch-'0';ch=getchar();}while(ch>='0'&&ch<='9');
return f*x;
}
int main(){
n=read();m=read();
for(int i=1;i<=n;i++){
val[i]=read();pos[val[i]]=i;
a1[i]=ask(n)-ask(val[i]);
ans+=a1[i];
for(int j=val[i];j<=n;j+=lowbit(j))c[j]++;
}
memset(c,0,sizeof(c));
for(int i=n;i;i--){
a2[i]=ask(val[i]-1);
for(int j=val[i];j<=n;j+=lowbit(j))c[j]++;
}
for(int i=1;i<=m;i++){
printf("%lld\n",ans);
int x=read();x=pos[x];
ans-=(a1[x]+a2[x]-querysub(1,x-1,val[x])-querypre(x+1,n,val[x]));
for(int j=x;j<=n;j+=lowbit(j))change(rt[j],1,n,val[x]);
}
return 0;
}
```