Sorry, your browser cannot access this site
This page requires browser support (enable) JavaScript
Learn more >

动态逆序对专练

题解

发布于：Apr 30, 2022

更新于：Aug 13, 2024

次浏览

就是三倍经验

题意

维护一个序列，每次修改后求出当前序列逆序对个数。

思路

题目让我们求出 \[ \sum_{i=1}^n\sum_{j=i+1}^n[a_i>a_j] \] 也就是让我们求出满足 \[ pos_i<pos_j\&\&a_i>a_j \] 的点对数量。

对于不修改的情况，这显然是一个三维偏序问题，用树状数组或归并处理都可以。

对于修改的情况，我们可以用CDQ分治离线解决，或者使用树套树在线处理。

我这么懒当然是用树套树啦~

树状数组套值域线段树

思想

树状数组维护序列，值域线段树维护值域。

优点是可以写成非递归式查询，常数相对较小。

缺点是即使是动态开点空间消耗仍然很大。

实现

具体实现是每个树状数组节点开一棵线段树。修改时修改所有树状数组上包括的线段树，查询时类似。

1
2
3
4
5
6
7
8
void update(int &ro,int l,int r,int x,int k){//l和r是当前值域区间，x为位置
    if(!ro) ro=++tot;
    val[ro]+=k;
    if(l==r)return;
    int mid=l+r>>1;
    if(x<=mid)update(ls[ro],l,mid,x,k);
    else update(rs[ro],mid+1,r,x,k);
}

墙裂安利非递归式线段树查询

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
inline long long query(int l,int r,int x,int type){
    int cnta=0,cntb=0;
    long long ans=0;
    for(int i=l-1;i;i-=i&-i) qa[++cnta]=rt[i];//树状数组查询方法：差分
    for(int i=r;i;i-=i&-i)   qb[++cntb]=rt[i];//先将所有要处理的树状数组上的线段树全部记录，然后一起查询
    l=1,r=n;
    while(l<r){
        int mid=l+r>>1;
        if(x>mid){
            if(type){//type表示查询的类型，按照正常线段树查询的思路处理即可。这里type=1表示查左边
                for(int i=1;i<=cnta;i++) ans-=val[ls[qa[i]]];
                for(int i=1;i<=cntb;i++) ans+=val[ls[qb[i]]];
            }
            for(int i=1;i<=cnta;i++) qa[i]=rs[qa[i]];
            for(int i=1;i<=cntb;i++) qb[i]=rs[qb[i]];
            l=mid+1;
        }else{
            if(!type){
                for(int i=1;i<=cnta;i++) ans-=val[rs[qa[i]]];
                for(int i=1;i<=cntb;i++) ans+=val[rs[qb[i]]];
            }
            for(int i=1;i<=cnta;i++) qa[i]=ls[qa[i]];
            for(int i=1;i<=cntb;i++) qb[i]=ls[qb[i]];
            r=mid;
        }
    }
    return ans;
}

例题

P3157 [CQOI2011]动态逆序对

给你一个排列，每次删除一个位置上的数，求每次操作后的逆序对数。

思路

插入原序列之后得到原序列答案，每次删除一个数 \(x\) 查询 \(pos_i<x\) 、\(a_i>a_x\) 和 \(pos_i>x\) 、\(a_i<a_x\) 的答案并用之前的答案减去，然后删除它的影响。

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
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cctype>
#include<algorithm>
#include<cmath>
using namespace std;
inline int read(){
	int w=0,x=0;char c=getchar();
	while(!isdigit(c))w|=c=='-',c=getchar();
	while(isdigit(c))x=(x<<3)+(x<<1)+(c^48),c=getchar();
	return w?-x:x;
}
namespace star
{
	const int maxn=1e5+10,maxm=3e7+10;
	int n,m,a[maxn],ls[maxm],rs[maxm],tot,rt[maxn],val[maxm];
	void update(int &ro,int l,int r,int x,int k){
		if(!ro) ro=++tot;
		val[ro]+=k;
		if(l==r)return;
		int mid=(l+r)>>1;
		if(x<=mid) update(ls[ro],l,mid,x,k);
		else update(rs[ro],mid+1,r,x,k);
	}
	int qa[maxn],qb[maxn];
	long long ans;
	inline long long query(int l,int r,int x,int type){
		int cnta=0,cntb=0;
		long long ans=0;
		for(int i=l-1;i;i-=i&-i) qa[++cnta]=rt[i];
		for(int i=r;i;i-=i&-i)   qb[++cntb]=rt[i];
		l=1,r=n;
		while(l<r){
			int mid=(l+r)>>1;
			if(x>mid){
				if(type){
					for(int i=1;i<=cnta;i++)ans-=val[ls[qa[i]]];
					for(int i=1;i<=cntb;i++)ans+=val[ls[qb[i]]];
				}
				for(int i=1;i<=cnta;i++)qa[i]=rs[qa[i]];
				for(int i=1;i<=cntb;i++)qb[i]=rs[qb[i]];
				l=mid+1;
			}else{
				if(!type){
					for(int i=1;i<=cnta;i++)ans-=val[rs[qa[i]]];
					for(int i=1;i<=cntb;i++)ans+=val[rs[qb[i]]];
				}
				for(int i=1;i<=cnta;i++)qa[i]=ls[qa[i]];
				for(int i=1;i<=cntb;i++)qb[i]=ls[qb[i]];
				r=mid;
			}
		}
		return ans;
	}
	int pos[maxn];
	inline void work(){
		n=read(),m=read();
		for(int i=1;i<=n;i++) {
			ans+=query(1,i-1,a[i]=read(),0);pos[a[i]]=i;
			for(int x=i;x<=n;x+=x&-x) update(rt[x],1,n,a[i],1);
		}
		printf("%lld\n",ans);
		while(--m){
			int x=read();
			ans-=query(1,pos[x]-1,x,0)+query(pos[x]+1,n,x,1);
			printf("%lld\n",ans);
			for(int j=pos[x];j<=n;j+=j&-j) update(rt[j],1,n,x,-1);
		}
	}
}
signed main(){
	star::work();
	return 0;
}

CF785E Anton and Permutation

给你一个原序列为递增排列的序列，每次交换两个位置上的数，求每次操作后的逆序对数。

思路

相对于上一题，并非删除而是交换两个位置上的数，实际上就是在原位置删除两个数然后在彼此的位置又加上这两个数。

这里我先减去影响然后更新再加上影响，最后单独讨论一下这两个数之间互换对答案的贡献。

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
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cctype>
#include<algorithm>
#include<cmath>
using namespace std;
inline int read(){
	int w=0,x=0;char c=getchar();
	while(!isdigit(c))w|=c=='-',c=getchar();
	while(isdigit(c))x=(x<<3)+(x<<1)+(c^48),c=getchar();
	return w?-x:x;
}
namespace star
{
	const int maxn=2e5+1,maxm=3e7+1;
	int n,Q,a[maxn],rt[maxn];
	long long ans;
	int ls[maxm],rs[maxm],tot,val[maxm];
	void update(int &ro,int l,int r,int x,int k){
		if(!ro) ro=++tot;
		val[ro]+=k;
		if(l==r)return;
		int mid=l+r>>1;
		if(x<=mid)update(ls[ro],l,mid,x,k);
		else update(rs[ro],mid+1,r,x,k);
	}
	int qa[maxn],qb[maxn];
	inline long long query(int l,int r,int x,int type){
		int cnta=0,cntb=0;
		long long ans=0;
		for(int i=l-1;i;i-=i&-i) qa[++cnta]=rt[i];
		for(int i=r;i;i-=i&-i)   qb[++cntb]=rt[i];
		l=1,r=n;
		while(l<r){
			int mid=l+r>>1;
			if(x>mid){
				if(type){
					for(int i=1;i<=cnta;i++) ans-=val[ls[qa[i]]];
					for(int i=1;i<=cntb;i++) ans+=val[ls[qb[i]]];
				}
				for(int i=1;i<=cnta;i++) qa[i]=rs[qa[i]];
				for(int i=1;i<=cntb;i++) qb[i]=rs[qb[i]];
				l=mid+1;
			}else{
				if(!type){
					for(int i=1;i<=cnta;i++) ans-=val[rs[qa[i]]];
					for(int i=1;i<=cntb;i++) ans+=val[rs[qb[i]]];
				}
				for(int i=1;i<=cnta;i++) qa[i]=ls[qa[i]];
				for(int i=1;i<=cntb;i++) qb[i]=ls[qb[i]];
				r=mid;
			}
		}
		return ans;
	}
	inline void work(){
		n=read(),Q=read();
		for(int i=1;i<=n;i++){
			a[i]=i;
			for(int j=i;j<=n;j+=j&-j) update(rt[j],1,n,a[i],1);
		}
		while(Q--){
			int x=read(),y=read();
			if(x==y){
				printf("%lld\n",ans);continue;
			}
			if(x>y)swap(x,y);
			ans=ans-query(1,x-1,a[x],0)-query(x+1,n,a[x],1)-query(1,y-1,a[y],0)-query(y+1,n,a[y],1);
			for(int i=x;i<=n;i+=i&-i) update(rt[i],1,n,a[x],-1),update(rt[i],1,n,a[y],1);
			for(int i=y;i<=n;i+=i&-i) update(rt[i],1,n,a[x],1),update(rt[i],1,n,a[y],-1);
			swap(a[x],a[y]);
			ans=ans+query(1,x-1,a[x],0)+query(x+1,n,a[x],1)+query(1,y-1,a[y],0)+query(y+1,n,a[y],1);
			ans+=(a[x]<a[y]?1:-1);
			printf("%lld\n",ans);
		}
	}
}
signed main(){
	star::work();
	return 0;
}

P1975 [国家集训队]排队

给你一个序列，每次交换两个位置上的数，求每次操作后逆序对数。

思路

给上面的代码加个离散化XD

后面单独讨论两个数的贡献时有一点区别。

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
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cctype>
#include<algorithm>
#include<cmath>
using namespace std;
inline int read(){
	int w=0,x=0;char c=getchar();
	while(!isdigit(c))w|=c=='-',c=getchar();
	while(isdigit(c))x=(x<<3)+(x<<1)+(c^48),c=getchar();
	return w?-x:x;
}
namespace star
{
	const int maxn=2e4+1,maxm=3e6+1;
	int n,Q,a[maxn],cnt,b[maxn],rt[maxn];
	long long ans;
	int ls[maxm],rs[maxm],tot,val[maxm];
	void update(int &ro,int l,int r,int x,int k){
		if(!ro) ro=++tot;
		val[ro]+=k;
		if(l==r)return;
		int mid=l+r>>1;
		if(x<=mid)update(ls[ro],l,mid,x,k);
		else update(rs[ro],mid+1,r,x,k);
	}
	int qa[maxn],qb[maxn];
	inline long long query(int l,int r,int x,int type){
		int cnta=0,cntb=0;
		long long ans=0;
		for(int i=l-1;i;i-=i&-i) qa[++cnta]=rt[i];
		for(int i=r;i;i-=i&-i)   qb[++cntb]=rt[i];
		l=1,r=n;
		while(l<r){
			int mid=l+r>>1;
			if(x>mid){
				if(type){
					for(int i=1;i<=cnta;i++) ans-=val[ls[qa[i]]];
					for(int i=1;i<=cntb;i++) ans+=val[ls[qb[i]]];
				}
				for(int i=1;i<=cnta;i++) qa[i]=rs[qa[i]];
				for(int i=1;i<=cntb;i++) qb[i]=rs[qb[i]];
				l=mid+1;
			}else{
				if(!type){
					for(int i=1;i<=cnta;i++) ans-=val[rs[qa[i]]];
					for(int i=1;i<=cntb;i++) ans+=val[rs[qb[i]]];
				}
				for(int i=1;i<=cnta;i++) qa[i]=ls[qa[i]];
				for(int i=1;i<=cntb;i++) qb[i]=ls[qb[i]];
				r=mid;
			}
		}
		return ans;
	}
	inline void work(){
		n=read();
		for(int i=1;i<=n;i++) a[i]=b[i]=read();
		sort(b+1,b+1+n);
		cnt=unique(b+1,b+1+n)-b-1;
		for(int i=1;i<=n;i++) a[i]=lower_bound(b+1,b+1+cnt,a[i])-b;
		for(int i=1;i<=n;i++){
			ans+=query(1,i-1,a[i],0);
			for(int j=i;j<=n;j+=j&-j) update(rt[j],1,n,a[i],1);
		}
		printf("%lld\n",ans);
		Q=read();
		while(Q--){
			int x=read(),y=read();
			if(x==y){
				printf("%lld\n",ans);continue;
			}
			if(x>y)swap(x,y);
			ans=ans-query(1,x-1,a[x],0)-query(x+1,n,a[x],1)-query(1,y-1,a[y],0)-query(y+1,n,a[y],1);
			for(int i=x;i<=n;i+=i&-i) update(rt[i],1,n,a[x],-1),update(rt[i],1,n,a[y],1);
			for(int i=y;i<=n;i+=i&-i) update(rt[i],1,n,a[x],1),update(rt[i],1,n,a[y],-1);
			swap(a[x],a[y]);
			ans=ans+query(1,x-1,a[x],0)+query(x+1,n,a[x],1)+query(1,y-1,a[y],0)+query(y+1,n,a[y],1);
			if(a[x]<a[y]) ans+=1;
			else if(a[x]>a[y]) ans-=1;
			printf("%lld\n",ans);
		}
	}
}
signed main(){
	star::work();
	return 0;
}

对于后两个题更简单并且更优秀的分块解法，我不会因为没有普适性所以我们不学，嗯嗯。

更新于：Aug 13, 2024

博客园

OI

逆序对

给小狼留言