GGAutomaton's Blog
0%

[CQOI2011]动态逆序对

发表于 分类于 ，

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

看到题目第一反应，树状数组乱搞？
位置线段树套权值树状数组？爆空间！

solution:
1.分块树状数组暴力，不讲
2.树套树
已知有两种写法
位置树状数组，权值线段树
权值树状数组，位置线段树
这里写权值树状数组，位置线段树

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
#include<iostream>
#include<cstdio>
#include<cstring>
#define maxsize 6000005
//动态开点，具体多小试试看
#define lowbit(x) x&-x
using namespace std;
typedef long long LL;
int root[maxsize],lson[maxsize],rson[maxsize],sum[maxsize],sz;
int val[100005],pos[100005];
int bb[100005],as[100005];//before_bigger after_smaller
LL ans;
int n,m;
inline int read() {
    int sum=0;char ch=0;
    while (ch>'9' || ch<'0') ch=getchar();
    while (ch>='0' && ch<='9') sum=sum*10+ch-'0',ch=getchar();
    return sum;
}
inline void update1(int x) {
    for (;x<=n;x+=lowbit(x)) root[x]++;
}
inline int getsum1(int x) {
	int sum=0;
    for (;x>0;x-=lowbit(x)) sum+=root[x];
    return sum;
}
int query(int pp,int l,int r,int ll,int rr) {
	if (pp==0) return 0;
	if (l==ll && r==rr) return sum[pp];
	int mid=(l+r)>>1;
	if (rr<=mid) return query(lson[pp],l,mid,ll,rr);
	if (ll>mid) return query(rson[pp],mid+1,r,ll,rr);
	return query(lson[pp],l,mid,ll,mid)+query(rson[pp],mid+1,r,mid+1,rr);
}
void update(int &pp,int l,int r,int ll) {
	if (pp==0) {
		pp=++sz;
		if (sz>=maxsize) puts("MLE");
	}
	sum[pp]++;
	if (l==r && l==ll) return;
	int mid=(l+r)>>1;
	if (ll<=mid) update(lson[pp],l,mid,ll);
	else update(rson[pp],mid+1,r,ll);
}
inline int query_bb(int v,int p) {//值比它大，在它前面 
	int sum1=0,sum2=0,x=n;
	for (;v;v-=lowbit(v)) sum1+=query(root[v],1,n,1,p);
	for (;x;x-=lowbit(x)) sum2+=query(root[x],1,n,1,p);
	return sum2-sum1;
}
inline int query_as(int v,int p) {//值比它小，在它后面 
	int sum=0;
	for (;v;v-=lowbit(v)) sum+=query(root[v],1,n,p,n);
	return sum;
}
inline void update2(int v,int p) {
	for (;v<=n;v+=lowbit(v)) update(root[v],1,n,p);
}
int main() {
	n=read();m=read();
	for (int i=1;i<=n;i++) {
		val[i]=read();
		pos[val[i]]=i;
		bb[i]=getsum1(n)-getsum1(val[i]);//借用一下root[] 
		ans+=bb[i];
		update1(val[i]);
	}
	memset(root,0,sizeof(root));
	for (int i=n;i>0;i--) {
		as[i]=getsum1(val[i]-1);
		update1(val[i]);
	}
	memset(root,0,sizeof(root));
	while (m--) {
		printf("%lld\n",ans);
		int v=read(),p=pos[v];
		ans-=(bb[p]+as[p]-query_as(v-1,p+1)-query_bb(v,p-1));
		update2(v,p);
	}
	return 0;
}

3.cdq分治
这是个锅，过几天补上