NKOJ 2041 （CQOI 2011）动态逆序对 （CDQ分治+树状数组/树套树）

发表于 |
字数统计: 1,352字 | 阅读时长 ≈ 8min

P2041【CQOI2011】动态逆序对

问题描述

对于序列A，它的逆序对数定义为满足i < j，且Ai > Aj的数对(i,j)的个数。给1到n的一个排列，按照某种顺序依次删除m个元素，你的任务是在每次删除一个元素之前统计整个序列的逆序对数。

输入格式

输入第一行包含两个整数n和m，即初始元素的个数和删除的元素个数。以下n行每行包含一个1到n之间的正整数，即初始排列。以下m行每行一个正整数，依次为每次删除的元素。

输出格式

输出包含m行，依次为删除每个元素之前，逆序对的个数。

样例输入

5 4
1
5
3
4
2
5
1
4
2

样例输出

5
2
2
1

数据范围

n <=100000
m <=50000

按照逆序对的定义，只需要支持查找前面比他大的和后面比他小的。

树套树的做法就不说了，我用的树状数组套主席树。

显然最优秀的做法是CDQ分治，离线倒序添加，将没删掉的点视为最先添加的，对添加时间分治，对x坐标排序，用树状数组维护y坐标即可。统计答案的时候求一下前缀和。

分治代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<cstring>
#define N 100005
using namespace std;
struct node{int x,y,id;}K[N],T[N];
int n,m,A[N],B[N],C[N];
bool mark[N];
long long Ans[N];
void MD(int x,int d)
{for(int i=x;i<=n;i+=(i&-i))C[i]+=d;}
int GS(int x)
{
	int sum=0,i;
	for(i=x;i;i-=(i&-i))sum+=C[i];
	return sum;
}
void CDQ(int l,int r)
{
	if(l==r)return;
	int i,j,k,sum=0,mid=l+r>>1;
	CDQ(l,mid);CDQ(mid+1,r);
	i=l;j=mid+1;k=0;
	while(i<=mid&&j<=r)
	{
		if(K[i].x<=K[j].x)T[++k]=K[i++];
		else T[++k]=K[j++];
	}
	while(i<=mid)T[++k]=K[i++];
	while(j<=r)T[++k]=K[j++];
	for(i=1;i<=k;i++)K[l+i-1]=T[i];
	for(i=l;i<=r;i++)
	{
		if(K[i].id<=mid)MD(K[i].y,1),sum++;
		else Ans[K[i].id]+=sum-GS(K[i].y);
	}
	for(i=l;i<=r;i++)if(K[i].id<=mid)MD(K[i].y,-1);
	for(i=r;i>=l;i--)
	{
		if(K[i].id<=mid)MD(K[i].y,1);
		else Ans[K[i].id]+=GS(K[i].y);
	}
	for(i=l;i<=r;i++)if(K[i].id<=mid)MD(K[i].y,-1);
}
int main()
{
	int i,j,k,x;
	scanf("%d%d",&n,&m);k=n;
	for(i=1;i<=n;i++)scanf("%d",&A[i]),B[A[i]]=i;
	for(i=1;i<=m;i++)
	{
		scanf("%d",&x);mark[B[x]]=1;
		K[k].x=B[x];K[k].y=x;K[k].id=k;k--;
	}
	for(i=1;i<=n;i++)if(!mark[i])K[k].x=i,K[k].y=A[i],K[k].id=k,k--;
	CDQ(1,n);
	for(i=1;i<=n;i++)Ans[i]+=Ans[i-1];
	for(i=n;i>n-m;i--)printf("%lld\n",Ans[i]);
}

树套树代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<cstring>
#define N 1000005
#define M 20000005
using namespace std;
int n,m,A[2][N],cnt[2],C[N],B[N],H[N];
int tot,rt[N],ls[M],rs[M],v[M];
long long ans;
int ADD(int p,int l,int r,int k,int d)
{
	if(!p)p=++tot;v[p]+=d;
	if(l==r)return p;
	int mid=l+r>>1;
	if(k<=mid)ls[p]=ADD(ls[p],l,mid,k,d);
	else rs[p]=ADD(rs[p],mid+1,r,k,d);
	return p;
}
void MD(int x,int y,int d)
{for(int i=x;i<=n;i+=(i&-i))rt[i]=ADD(rt[i],1,n,y,d);}
void GS(int x,int d)
{for(int i=x;i;i-=(i&-i))A[d][++cnt[d]]=rt[i];}
void md(int x,int d)
{for(int i=x;i<=n;i+=(i&-i))C[i]+=d;}
int gs(int x)
{
	int i,sum=0;
	for(i=x;i;i-=(i&-i))sum+=C[i];
	return sum;
}
void Gmax(int l,int r,int k)
{
	if(l==r)
	{
		if(l<k)return;
		for(int i=1;i<=cnt[0];i++)ans-=v[A[0][i]];
		return;
	}
	int i,mid=l+r>>1;
	if(k<=mid)
	{
		for(i=1;i<=cnt[0];i++)ans-=v[rs[A[0][i]]],A[0][i]=ls[A[0][i]];
		Gmax(l,mid,k);
	}
	else
	{
		for(i=1;i<=cnt[0];i++)A[0][i]=rs[A[0][i]];
		Gmax(mid+1,r,k);
	}
}
void Gmin(int l,int r,int k)
{
	if(l==r)
	{
		if(l>k)return;
		for(int i=1;i<=cnt[0];i++)ans-=v[A[0][i]];
		for(int i=1;i<=cnt[1];i++)ans+=v[A[1][i]];
		return;
	}
	int i,mid=l+r>>1;
	if(k>mid)
	{
		for(i=1;i<=cnt[0];i++)ans-=v[ls[A[0][i]]],A[0][i]=rs[A[0][i]];
		for(i=1;i<=cnt[1];i++)ans+=v[ls[A[1][i]]],A[1][i]=rs[A[1][i]];
		Gmin(mid+1,r,k);
	}
	else
	{
		for(i=1;i<=cnt[0];i++)A[0][i]=ls[A[0][i]];
		for(i=1;i<=cnt[1];i++)A[1][i]=ls[A[1][i]];
		Gmin(l,mid,k);
	}
}
void Work(int x)
{
	printf("%lld\n",ans);
	int y=H[x];MD(y,x,-1);
	cnt[0]=cnt[1]=0;GS(y,0);
	Gmax(1,n,x);
	cnt[0]=cnt[1]=0;
	GS(n,0);GS(y,1);
	Gmin(1,n,x);
}
int main()
{
	int i,x;
	scanf("%d%d",&n,&m);
	for(i=1;i<=n;i++)scanf("%d",&B[i]),H[B[i]]=i;
	for(i=1;i<=n;i++)
	{
		ans+=i-1-gs(B[i]);
		md(B[i],1);
		MD(i,B[i],1);
	}
	for(i=1;i<=m;i++)
	{
		scanf("%d",&x);
		Work(x);
	}
}