``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=,f=;char ch=getchar();
while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}
while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}
return x*f;
}
#define maxn 12200005
long long tmp = ;
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,,sizeof(root));
sz=;
}
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]=;ls[k]=rs[k]=;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]>){
w[k]--;
s[k]--;
return;
}
if(ls[k]*rs[k]==)
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+;x+=lowbit(x))
Tr.Insert(Tr.root[x],v);
}
void Bit_change(int x,int v)
{
for(;x<=n+;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[];
int lowbit(int x)
{
return x&(-x);
}
int query(int x)
{
int ans = ;
for(;x;x-=lowbit(x))
ans+=a[x];
return ans;
}
void updata(int x,int v)
{
for(;x<;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,,sizeof(bit2.a));
Tr.init();
memset(bit.a,,sizeof(bit.a));
long long Res = ;
for(int i=;i<=n;i++)
{
a[i]=read();
Bit_updata(i,a[i]);
bit.updata(a[i],);
Res += (i-bit.query(a[i]-)-);
pos[a[i]]=i;
}
memset(bit.a,,sizeof(bit.a));
for(int i=;i<=n;i++)
bit.updata(i,),bit2.updata(i,);
for(int i=;i<=m;i++)
{
printf("%lld\n",Res);
int x;scanf("%d",&x);
long long ans1 = bit2.query(x)-;//总共有多少数比他小
Bit_query(pos[x],x);long long ans2 = tmp;tmp=;ans2--;//在他前面有多少比他小
long long ans3 = bit.query(pos[x])-;//在他前面一共有多少个数
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,-);
bit.updata(pos[x],-);
}
}
}