P3157 [CQOI2011]动态逆序对[cdq分治]

题目描述

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

输入输出格式

输入格式:

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

输出格式:

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

输入输出样例

输入样例#1:

1
2
3
4
5
6
7
8
9
10
5 4
1
5
3
4
2
5
1
4
2

输出样例#1

1
2
3
4
5
2
2
1

说明

样例解释
$(1,5,3,4,2)(1,3,4,2)(3,4,2)(3,2)(3)$。

$N\le 100000$ ,$M\le50000$

题解

考虑删除一个数$i$ ,$i$对答案的影响只有$i$产生的贡献和$i$对后面产生的影响

$x$:删除时间,$y$:位置,$z$:权值

求$i’$的逆序对:$x>x’$,$y<y’$,$z>z’$,求出一个答案$f_i$

考虑 $i’$ 对后面的影响:$x>x’$,$y>y’$,$z<z’$,求出一个答案$g_i$

对于最后没有删除的点,根据位置随便加一个删除时间。

然后就是三位偏序了。

求 $f_i$ ,按照删除时间从大到小排序,左边排 $z$ ,树状数组更 $y$

求 $g_i$ ,按照删除时间从大到小排序,左边排 $y$ ,树状数组更 $z$

最后扫一遍,更答案。

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
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
// luogu-judger-enable-o2
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int qmax(int &x,int y) {if (x<y) x=y;}
int qmin(int &x,int y) {if (x>y) x=y;}
int read()
{
char s;
int k=0,base=1;
while((s=getchar())!='-'&&s!=EOF&&!(isdigit(s)));
if(s=='-')base=-1,s=getchar();
while(isdigit(s))
{
k=k*10+(s^'0');
s=getchar();
}
return k*base;
}
void write(ll x)
{
if(x<0)
{
putchar('-');
write(-x);
}
else
{
if(x/10) write(x/10);putchar(x%10+'0');
}
}
const int maxn=1e5+100;
const int maxm=5e4+100;
int n,m;
int b[maxn],c[maxn];
int t[maxn];
ll ans;
struct node
{
int x,y,z;//x:删除的时间 y:pos z:值
int f,g;
} a[maxn],A[maxn];

inline void xg(int x,int y)
{
while (x<=n)
{
*(t+x)+=y;
x+=x&(-x);
}
}
inline int qsum(int x)
{
int sum=0;
while (x)
{
sum+=*(t+x);
x-=x&(-x);
}
return sum;
}

bool cmp(node aa,node bb)//按照位置排序
{
return aa.y<bb.y;
}
bool cmp1(node aa,node bb)//按照删除时间排
{
return aa.x>bb.x;
}
bool cmp2(node aa,node bb)
{
return aa.x<bb.x;
}
void cdq(int x,int y)
{
if (x==y) return;
int mid=(x+y)>>1;
cdq(x,mid);cdq(mid+1,y);
int l=x,r=mid+1,p=0;
while (r<=y)
{
while (l<=mid&&a[l].z>a[r].z) {xg(a[l].y,1);l++;}
a[r].f+=qsum(a[r].y);
r++;
}
for (int i=x;i<l;i++) xg(a[i].y,-1);

l=x,r=mid+1,p=x-1;
while (l<=mid&&r<=y)
{
if (a[l].z>a[r].z) A[++p]=a[l++]; else A[++p]=a[r++];
}
while (l<=mid) A[++p]=a[l++];
while (r<=y) A[++p]=a[r++];
for (int i=x;i<=y;i++) a[i]=A[i];
}
void CDQ(int x,int y)
{
if (x==y) return;
int mid=(x+y)>>1;
CDQ(x,mid);CDQ(mid+1,y);
int l=x,r=mid+1,p=0;
while (r<=y)
{
while (l<=mid&&a[l].y>a[r].y) {xg(a[l].z,1);l++;}
a[r].g+=qsum(a[r].z);
r++;
}
for (int i=x;i<l;i++) xg(a[i].z,-1);//memset太慢了,不如一个个清

l=x,r=mid+1,p=x-1;//按照y的大小合并
while (l<=mid&&r<=y)
{
if (a[l].y>a[r].y) A[++p]=a[l++]; else A[++p]=a[r++];
}
while (l<=mid) A[++p]=a[l++];
while (r<=y) A[++p]=a[r++];
for (int i=x;i<=y;i++) a[i]=A[i];
}
int main()
{
n=read();m=read();//a数组初始按值排序
for (int i=1;i<=n;i++)
{
*(b+i)=read();
a[b[i]].y=i;
a[b[i]].z=b[i];
ans+=i-1-qsum(b[i]);
xg(b[i],1);
}
memset(t,0,sizeof(t));
for (int i=1;i<=m;i++)
{
*(c+i)=read();
a[c[i]].x=i;
}
sort(a+1,a+n+1,cmp);
for (int i=1,j=m+1;i<=n;i++)
{
if (a[i].x==0) a[i].x=j++;
}
sort(a+1,a+n+1,cmp1);
cdq(1,n);//求出f[i]
sort(a+1,a+n+1,cmp1);
CDQ(1,n);//求出g[i]
sort(a+1,a+n+1,cmp2);
for (int i=1;i<=m;i++)
{
write(ans);
putchar('\n');
ans=ans-(ll)a[i].f-(ll)a[i].g;
}
return 0;
}