``Dynamic'' Inversion
Time Limit: 20 Sec
Memory Limit: 256 MB
题目连接
https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=3141
Description
You are given a permutation f1,2,3,. . . ,ng. Remove m of them one by one, and output the number of
inversion pairs before each removal. The number of inversion pairs of an array A is the number of
ordered pairs (i; j) such that i < j and A[i] > A[j].
Input
The input contains several test cases. The rst line of each case contains two integers n and m
(1 n 200;000, 1 m 100;000). After that, n lines follow, representing the initial permutation.
Then m lines follow, representing the removed integers, in the order of the removals. No integer will
be removed twice. The input is terminated by end-of- le (EOF).
Output
For each removal, output the number of inversion pairs before it.
Explanation: (1,5,3,4,2)->(1,3,4,2)->(3,4,2)->(3,2)->(3)
Sample Input
5 4
1
5
3
4
2
5
1
4
2
Sample Output
5
2
2
1
HINT
题意
给你n个数，然后有m次操作，每次操作可以删除一个数
然后问你每次删除之前，还有多少个逆序对
题解：
对于每个数关于逆序对的贡献，就是
这个数前面有多少个数比他大，后面有多少个数比他小
这就是贡献~
然后我们就树状数组套treap来维护这些信息就好了
线段树会TLE。。。
代码：
#include<iostream> #include<stdio.h> #include<algorithm> #include<cstring> #include<ctime> using namespace std; inline long long read() { long long x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } #define maxn 12200005 long long tmp = 0; int a[maxn]; int pos[maxn]; int n,m; ////////////////treap struct Treap { int root[maxn],sz,s[maxn],ls[maxn],rs[maxn],v[maxn],w[maxn],rnd[maxn]; void init() { memset(root,0,sizeof(root)); sz=0; } void Updata(int k) { s[k]=s[ls[k]]+s[rs[k]]+w[k]; } void Rturn(int &k) { int t; t=ls[k],ls[k]=rs[t],rs[t]=k,s[t]=s[k]; Updata(k);k=t; } void Lturn(int &k) { int t; t=rs[k],rs[k]=ls[t],ls[t]=k,s[t]=s[k]; Updata(k);k=t; } void Insert(int &k,int num) { if(!k) { k=++sz;s[k]=w[k]=1;ls[k]=rs[k]=0;rnd[k]=rand(); v[k]=num;return; } s[k]++; if(v[k]==num)w[k]++; else if(num<v[k]) { Insert(ls[k],num); if(rnd[ls[k]]<rnd[k]) Rturn(k); } else { Insert(rs[k],num); if(rnd[rs[k]]<rnd[k]) Lturn(k); } } void Del(int &k,int num) { if(v[k]==num) { if(w[k]>1){ w[k]--; s[k]--; return; } if(ls[k]*rs[k]==0) k=ls[k]+rs[k]; else if(rnd[ls[k]]<rnd[rs[k]]) Rturn(k),Del(k,num); else Lturn(k),Del(k,num); } else if(num<v[k]){ Del(ls[k],num); s[k]--; } else{ Del(rs[k],num); s[k]--; } } void Find(int k,int num) { if(!k)return; if(v[k]<=num){ tmp+=s[ls[k]]+w[k]; Find(rs[k],num); } else Find(ls[k],num); } }Tr; ///////////////////// /////////////////////线段树 int lowbit(int x) { return x&(-x); } void Bit_updata(int x,int v) { for(;x<=n+10;x+=lowbit(x)) Tr.Insert(Tr.root[x],v); } void Bit_change(int x,int v) { for(;x<=n+10;x+=lowbit(x)) Tr.Del(Tr.root[x],v); } void Bit_query(int x,int num) { for(;x;x-=lowbit(x)) Tr.Find(Tr.root[x],num); } /////////////////////////// ///////////////////////////树状数组 struct Bit { int a[400005]; int lowbit(int x) { return x&(-x); } int query(int x) { int ans = 0; for(;x;x-=lowbit(x)) ans+=a[x]; return ans; } void updata(int x,int v) { for(;x<400005;x+=lowbit(x)) a[x]+=v; } }bit,bit2; /////////////////////////// int main() { //freopen("a+b.in","r",stdin); srand(time(NULL)); while(scanf("%d%d",&n,&m)!=EOF) { memset(bit2.a,0,sizeof(bit2.a)); Tr.init(); memset(bit.a,0,sizeof(bit.a)); long long Res = 0; for(int i=1;i<=n;i++) { a[i]=read(); Bit_updata(i,a[i]); bit.updata(a[i],1); Res += (i-bit.query(a[i]-1)-1); pos[a[i]]=i; } memset(bit.a,0,sizeof(bit.a)); for(int i=1;i<=n;i++) bit.updata(i,1),bit2.updata(i,1); for(int i=1;i<=m;i++) { printf("%lld ",Res); int x;scanf("%d",&x); long long ans1 = bit2.query(x)-1;//总共有多少数比他小 Bit_query(pos[x],x);long long ans2 = tmp;tmp=0;ans2--;//在他前面有多少比他小 long long ans3 = bit.query(pos[x])-1;//在他前面一共有多少个数 long long Ans1 = ans3 - ans2;//前面有多少个数比他大 long long Ans2 = ans1 - ans2;//后面有多少个数比他小 //cout<<ans1<<" "<<ans2<<" "<<ans3<<endl; //cout<<Ans1<<" "<<Ans2<<endl; Res = Res-Ans1-Ans2; Bit_change(pos[x],x); bit2.updata(x,-1); bit.updata(pos[x],-1); } } }