静态逆序对

「洛谷」P1908

经典做法

考虑给定一个值不变的数组,怎么求出逆序对数量?
经典的做法是归并排序,另一种做法就是利用线段树或者树状数组,每次插入一个数询问其对答案的贡献
元素值太大时注意要离散化或者动态开点
这里先贴一份动态开点的代码

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
#include <bits/stdc++.h>
using namespace std;

const int maxn=1e7+5;
#define ll long long

struct Tree
{
int cnt,ls[maxn],rs[maxn],sum[maxn];

int query(int rt,int ql,int qr,int l=1,int r=1e9)
{
if(!rt) return 0;
if(l==ql && r==qr) return sum[rt];
int mid=(l+r)>>1;
if(qr<=mid) return query(ls[rt],ql,qr,l,mid);
if(ql>=mid+1) return query(rs[rt],ql,qr,mid+1,r);
return query(ls[rt],ql,mid,l,mid)+query(rs[rt],mid+1,qr,mid+1,r);
}

void add(int &rt,int pos,int val,int l=1,int r=1e9)
{
if(!rt) rt=++cnt;
if(l==r){sum[rt]+=val;return;}
int mid=(l+r)>>1;
if(pos<=mid) add(ls[rt],pos,val,l,mid);
else add(rs[rt],pos,val,mid+1,r);
sum[rt]=sum[ls[rt]]+sum[rs[rt]];
}
}T;

int main()
{
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);

int n;cin>>n;
ll ans=0;
int rt=0;
for(int i=1;i<=n;i++)
{
int x;cin>>x;
ans+=T.query(rt,x+1,1e9);
T.add(rt,x,1);
}
cout<<ans;
return 0;
}

字典树

那能否用字典树来求逆序对?答案是显然的
我们设 $val$ 为元素大小,$pos$ 为元素位置
我们把所有数插入一棵字典树中,那么对于一个节点,他的左儿子中的 $val$ 一定小于右儿子的 $val$,所以我们只需要统计左儿子中的 $pos$ 大于右儿子中的 $pos$ 的元素个数,累加即可
注意这样求出的逆序对的两个元素分别位于两棵子树,那位于同一棵子树中的逆序对数怎么求解?
按照 $CDQ$ 分治的思想,递归解决即可
注意这种写法如果题目给的空间很小,很容易 $MLE$

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
#include <bits/stdc++.h>
using namespace std;

const int maxn=5e5+5;
const int maxd=35;
#define ll long long

ll Ans;

struct Trie
{
int cnt=0;
int ch[maxn*maxd][2];
vector<int>vec[maxn*maxd];

void insert(ll x,int pos)
{
int rt=0;
for(int i=30;i>=0;i--)
{
int v=(x>>i)&1;
int &now=ch[rt][v];
if(!now) now=++cnt;
vec[now].push_back(pos);
rt=now;
}
}

void dfs(int pos,int rt)
{
int ls=ch[rt][0],rs=ch[rt][1];
if(ls) dfs(pos-1,ls);
if(rs) dfs(pos-1,rs);

int r=0;
int lsize=vec[ls].size();
int rsize=vec[rs].size();
for(int l=0;l<lsize;l++)
{
while(r<rsize && vec[ls][l]>vec[rs][r]) r++;
Ans+=r;
}
}
}T;

int main()
{
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);

int n;cin>>n;
for(int x,i=1;i<=n;i++) cin>>x,T.insert(x,i);
T.dfs(30,0);
cout<<Ans;
return 0;
}

动态逆序对

「洛谷」P3157

CDQ分治

现在这个数组变成动态的了,最初的逆序对数很容易求出,但难点就在于删除元素
删除一个元素很简单,只需要统计前面比它大和后面比它小的元素个数即可,但删除多个呢
一种很经典的解法是 $CDQ$ 分治
我们用一个三元组 $(time,val,pos)$ 来表示一个元素,$time$ 表示元素被删除的时间,$val$ 表示元素的值,$pos$ 表示元素的位置
那么能和元素j组成逆序对的元素i必须满足
$time_i < time_j$,$pos_i < pos_j$,$val_i > val_j$
或者 $time_i < time_j$,$pos_i > pos_j$,$val_i < val_j$
这就变成了经典的三维偏序问题

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
#include <bits/stdc++.h>
using namespace std;

const int maxn=2e5+5;
#define ll long long

int n,m;
struct BIT
{
ll sum[maxn];
#define lowbit(x) (x&-x)

void add(int x,int val)
{
while(x<=n) sum[x]+=val,x+=lowbit(x);
}

ll query(int x)
{
int res=0;
while(x) res+=sum[x],x-=lowbit(x);
return res;
}
}T;

struct Node
{
int op,v,p,id,t;
bool operator < (Node &B){return p<B.p;}
}A[maxn];
int cnt,val[maxn],pos[maxn];
ll ans[maxn];

void deal(int l,int r)
{
if(l==r) return;
int mid=(l+r)>>1;
deal(l,mid);deal(mid+1,r);
sort(A+l,A+mid+1);
sort(A+mid+1,A+r+1);

int j=l;
for(int i=mid+1;i<=r;i++)
{
while(j<=mid && A[j].p<=A[i].p) T.add(A[j].v,A[j].op),j++;
ans[A[i].id]+=(T.query(n)-T.query(A[i].v))*A[i].op;
}
for(int i=l;i<j;i++) T.add(A[i].v,-A[i].op);
j=mid;
for(int i=r;i>=mid+1;i--)
{
while(j>=l && A[j].p>=A[i].p) T.add(A[j].v,A[j].op),j--;
ans[A[i].id]+=T.query(A[i].v-1)*A[i].op;
}
for(int i=mid;i>j;i--) T.add(A[i].v,-A[i].op);
}

int main()
{
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);

cin>>n>>m;
for(int i=1;i<=n;i++)
{
cin>>val[i];
pos[val[i]]=i;
A[++cnt]=(Node){1,val[i],i,0,cnt};
}
for(int i=1;i<=m;i++)
{
int x;cin>>x;
A[++cnt]=(Node){-1,x,pos[x],i,cnt};
}
deal(1,cnt);
for(int i=1;i<=m;i++) ans[i]+=ans[i-1];
for(int i=0;i<m;i++) cout<<ans[i]<<'\n';
return 0;
}

带修主席树

很显然,$CDQ$ 分治只能离线处理,如果要求强制在线呢?
回顾删除一个元素的过程,删除一个元素,只需要统计前面比它大和后面比它小的元素个数即可
很明显的区间查询问题,主席树可做
那么要修改呢,当然是带修主席树,也就是树状数组套线段树

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
#include <bits/stdc++.h>
using namespace std;

const int maxn=1e5+5;
const int maxm=1e3+5;
#define ll long long

struct Tree
{
int RT[maxn],Ncnt,Top;
int L[maxn],R[maxn],Lcnt,Rcnt;
int ls[maxn<<7],rs[maxn<<7],sum[maxn<<7];
vector<int>TL[maxm],TR[maxm];

int limit;
inline int lowbit(int x){return x&(-x);}

void update(int &rt,int l,int r,int x,int v)
{
if(!rt) rt=++Ncnt;
sum[rt]+=v;
if(l==r) return;
int mid=(l+r)>>1;
if(x<=mid) update(ls[rt],l,mid,x,v);
else update(rs[rt],mid+1,r,x,v);
}

inline void add(int pos,int x,int v)
{
for(int i=pos;i<=limit;i+=lowbit(i)) update(RT[i],1,limit,x,v);
}

int query(int ql,int qr,int l,int r)
{
int res=0,mid=(l+r)>>1;
for(int i=1;i<=Lcnt;i++) res-=sum[L[i]];
for(int i=1;i<=Rcnt;i++) res+=sum[R[i]];
if(ql==l && qr==r) return res;

if(qr<=mid)
{
for(int i=1;i<=Lcnt;i++) L[i]=ls[L[i]];
for(int i=1;i<=Rcnt;i++) R[i]=ls[R[i]];
return query(ql,qr,l,mid);
}
else if(ql>=mid+1)
{
for(int i=1;i<=Lcnt;i++) L[i]=rs[L[i]];
for(int i=1;i<=Rcnt;i++) R[i]=rs[R[i]];
return query(ql,qr,mid+1,r);
}
else
{
res=0;
int now=Top++;
TL[now].clear();TR[now].clear();
for(int i=1;i<=Lcnt;i++) TL[now].push_back(L[i]);
for(int i=1;i<=Rcnt;i++) TR[now].push_back(R[i]);

for(int i=1;i<=Lcnt;i++) L[i]=ls[TL[now][i-1]];
for(int i=1;i<=Rcnt;i++) R[i]=ls[TR[now][i-1]];
res+=query(ql,mid,l,mid);

for(int i=1;i<=Lcnt;i++) L[i]=rs[TL[now][i-1]];
for(int i=1;i<=Rcnt;i++) R[i]=rs[TR[now][i-1]];
res+=query(mid+1,qr,mid+1,r);
return res;
}
}

int ask(int l,int r,int ql,int qr)
{
if(ql>qr || l>r) return 0;
Lcnt=Rcnt=Top=0;
for(int i=l-1;i;i-=lowbit(i)) L[++Lcnt]=RT[i];
for(int i=r;i;i-=lowbit(i)) R[++Rcnt]=RT[i];
return query(ql,qr,1,limit);
}
}T;

int pos[maxn];

int main()
{
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);

int n,m;
cin>>n>>m;
ll ans=0;
T.limit=n;
for(int i=1;i<=n;i++)
{
int x;cin>>x;
pos[x]=i;
ans+=T.ask(1,i-1,x+1,n);
T.add(i,x,1);
}
for(int i=1;i<=m;i++)
{
int x;cin>>x;
cout<<ans<<'\n';
ans-=T.ask(1,pos[x]-1,x+1,n);
ans-=T.ask(pos[x]+1,n,1,x-1);
T.add(pos[x],x,-1);
}
return 0;
}

字典树套树状数组

再回顾一下前面被卡空间的字典树做法,这道题给的空间相对来说大了很多
于是我们可以对字典树上的每一个节点开一个树状数组,同时进行离散化
也就是字典树套树状数组
显然,这种做法也不能强制在线,因为要分配空间,所以说,主席树大法好

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
#include <bits/stdc++.h>
using namespace std;

const int maxn=1e5+5;
const int maxm=1e7+5;
const int maxd=35;
#define ll long long

ll Ans;
int Pos[maxn],result[maxm];
int *POS;

struct BIT
{
int *sum,lim;
#define lowbit(x) (x&-x)

void add(int x,int val)
{
while(x<=lim) sum[x]+=val,x+=lowbit(x);
}

int query(int x)
{
int res=0;
while(x) res+=sum[x],x-=lowbit(x);
return res;
}
}N[maxn*maxd];

struct Trie
{
int cnt=0;
int ch[maxn*maxd][2];
vector<int>vec[maxn*maxd];

void insert(ll x,int pos)
{
int rt=0;
for(int i=30;i>=0;i--)
{
int v=(x>>i)&1;
int &now=ch[rt][v];
if(!now) now=++cnt;
vec[now].push_back(pos);
rt=now;
}
}

void build(int pos,int rt)
{
int ls=ch[rt][0],rs=ch[rt][1];
if(ls) build(pos-1,ls);
if(rs) build(pos-1,rs);

int len=vec[rt].size();
int lsize=vec[ls].size();
int rsize=vec[rs].size();
int r=0;
for(int l=0;l<lsize;l++)
{
while(r<rsize && vec[ls][l]>vec[rs][r]) r++;
Ans+=r;
}
N[rt].lim=len;
N[rt].sum=POS;
POS+=len+1;
for(int i=1;i<=len;i++) N[rt].add(i,1);
}

int find(int rt,int pos)
{
return lower_bound(vec[rt].begin(),vec[rt].end(),pos)-vec[rt].begin()+1;
}

void cut(ll x,int pos)
{
int rt=0;
for(int i=30;i>=0;i--)
{
int v=(x>>i)&1;
int now=ch[rt][v];
int ls=ch[rt][0],rs=ch[rt][1];
int p=find(now,pos);
N[now].add(p,-1);
if(v==0 && rs) p=find(rs,pos)-1,Ans-=N[rs].query(p);
if(v==1 && ls) p=find(ls,pos)-1,Ans-=N[ls].query(N[ls].lim)-N[ls].query(p);
rt=now;
}
}
}T;

int main()
{
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);

int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++)
{
ll x;cin>>x;
Pos[x]=i;
T.insert(x,i);
}
POS=result;
T.build(30,0);
for(int i=1;i<=m;i++)
{
ll x;cin>>x;
cout<<Ans<<'\n';
T.cut(x,Pos[x]);
}
return 0;
}