隐藏
「CQOI2011」动态逆序对 - CDQ分治三维偏序 | Bill Yang's Blog

路终会有尽头,但视野总能看到更远的地方。

0%

「CQOI2011」动态逆序对 - CDQ分治三维偏序

题目大意

给一个序列,动态删除一些数,求删除元素前整个序列的逆序对数。


题目分析

若不包含删除操作,那此题就是一个二维偏序问题。
满足$i\lt j$且$a_i\gt a_j$的个数,树状数组维护即可。(因为编号已经有序,所以不需排序)

但是我们有删除操作怎么办呢?那么我们加入时间轴代表删除操作,时间轴$t$前表示在执行某次删除操作前的情况。

显然,这是一个三维偏序问题,我们可以用CDQ分治维护时间维。
关于三维偏序可以看这两篇文章:传送门1传送门2

但是CDQ无法进行删除操作,只能将时间轴倒过来执行添加操作。

另外,此题不是维护全局答案也不是维护动规,所以我们对每一个询问的点需要考虑两边的影响。
对时间分为左右两部分后,$x$分别有序,那么我们需要统计在左半部分中比右半部分询问点$x$小且$y$大的数,以及在左半部分中比右半部分$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
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
102
103
104
#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;
typedef long long LL;
inline const LL Get_Int() {
LL num=0,bj=1;
char x=getchar();
while(x<'0'||x>'9') {
if(x=='-')bj=-1;
x=getchar();
}
while(x>='0'&&x<='9') {
num=num*10+x-'0';
x=getchar();
}
return num*bj;
}
const int maxn=200005;
LL n,m,pos[maxn],Ans[maxn];
struct BIT {
LL c[maxn];
#define lowbit(x) x&(-x)
void add(int x,int v) {
for(int i=x; i<=n; i+=lowbit(i))c[i]+=v;
}
void clear(int x) {
for(int i=x; i<=n; i+=lowbit(i))c[i]=0;
}
int sum(int x) {
int sum=0;
for(int i=x; i>=1; i-=lowbit(i))sum+=c[i];
return sum;
}
} bit;
struct Pair {
int x,y,t;
bool operator < (const Pair& b) const {
return x<b.x||(x==b.x&&y>b.y)||(x==b.x&&y==b.y&&t<b.t);
}
} a[maxn],tmp[maxn];
void CDQBinary(int Left,int Right) {
if(Left==Right)return;
int mid=(Left+Right)>>1;
int lpos=Left,rpos=mid+1;
for(int i=Left; i<=Right; i++)
if(a[i].t<=mid)tmp[lpos++]=a[i];
else tmp[rpos++]=a[i];
for(int i=Left; i<=Right; i++)a[i]=tmp[i];
CDQBinary(Left,mid);
int j=Left;
for(int i=mid+1; i<=Right; i++) { //左边比i大的
while(j<=mid&&a[j]<a[i]) {
bit.add(a[j].y,1);
j++;
}
Ans[a[i].t]+=bit.sum(n)-bit.sum(a[i].y);
}
for(int i=Left; i<=mid; i++)bit.clear(a[i].y);
j=mid;
for(int i=Right; i>mid; i--) { //右边比i小的
while(j>=Left&&a[i]<a[j]) {
bit.add(a[j].y,1);
j--;
}
Ans[a[i].t]+=bit.sum(a[i].y-1);
}
for(int i=Left; i<=mid; i++)bit.clear(a[i].y);
CDQBinary(mid+1,Right);
merge(a+Left,a+mid+1,a+mid+1,a+Right+1,tmp);
int tot=0;
for(int i=Left; i<=Right; i++)a[i]=tmp[tot++];
}
int main() {
n=Get_Int();
m=Get_Int();
for(int i=1; i<=n; i++) {
a[i].x=i;
a[i].y=Get_Int();
pos[a[i].y]=i;
}
int cnt=n;
LL ans=0;
for(int i=1; i<=m; i++) {
int x=Get_Int();
a[pos[x]].t=cnt--;
}
for(int i=1; i<=n; i++) //CDQ维度保证无重复
if(!a[i].t)a[i].t=cnt--;
sort(a+1,a+n+1);
CDQBinary(1,n);
for(int i=1; i<=n; i++)ans+=Ans[i];
for(int i=n; i>n-m; i--) {
printf("%lld\n",ans);
ans-=Ans[i];
}
return 0;
}
姥爷们赏瓶冰阔落吧~