P8449 [LSOT-1] 逆序对

题目背景

逆序对真好玩

题目描述

你需要维护一个数列，支持以下 $4$ 种操作：

1. 区间交换；
2. 把一个区间向后移动到第 $k$ 个数字与第 $k+1$ 个数字之间；
3. 在最后插入一个数 $x$；
4. 在开头插入一个数 $x$。

每个数数的序号为新序列重新从第一个数到第 $k$ 个数编号为 $1$ 到 $k$。

现在每次操作过后，请你输出整个数列逆序对数量的奇偶性。

输入格式

第一行输入两个正整数 $n,m$，表示初始序列的长度与操作个数。

接下来一行输入 $n$ 个正整数 $a_1,a_2,\dots ,a_n$，表示初始序列。

接下来 $m$ 行，每行先输入一个 $t$ 表示操作编号，之后：

• 若 $t=1$，则输入四个正整数 $l_1,r_1,l_2,r_2$，表示将区间 $[l_1,r_1]$ 与区间 $[l_2,r_2]$ 整体交换，保证 $l_1\le r_1<l_2\le r_2$；
• 若 $t=2$，则输入三个正整数 $l,r,k$，表示将区间 $[l,r]$ 移动至序列的第 $k$ 个数与第 $k+1$ 个数之间，保证 $r<k$；
• 若 $t=3$，则输入一个正整数 $x$，表示将 $x$ 插入到序列末端；
• 若 $t=4$，则输入一个正整数 $x$，表示将 $x$ 插入到序列首端。

输出格式

对于每一个指令执行后，如果逆序对数量是偶数，请输出 even ，否则输出 odd。

输入输出样例 #1

输入 #1

6 4
4 3 5 7 2 6
1 1 1 2 2
2 1 1 3
3 11
4 1

输出 #1

odd
odd
odd
odd

说明/提示

【样例解释】

第一次操作将区间 $[1,1]$ 和区间 $[2,2]$ 交换，序列变为 3 4 5 7 2 6。

第二次操作将区间 $[1,1]$ 移动到第 $3$ 和第 $4$ 个数中间。序列变为 4 5 3 7 2 6。

第三次操作在序列末端插入 $11$，序列变为 4 5 3 7 2 6 11。

第四次操作在序列开头插入 $1$，序列变为 1 4 5 3 7 2 6 11。

【数据范围】

「本题采用捆绑测试」

• $\text{Subtask 1(10 pts): }n,m\le 10^2$；
• $\text{Subtask 2(15 pts): }n,m\le 10^3$；
• $\text{Subtask 3(20 pts): }$没有一二操作；
• $\text{Subtask 4(20 pts): }$没有三四操作；
• $\text{Subtask 5(35 pts): }$无特殊限制。

对于 $100\%$ 的数据，$1\le n,m\le 2\times 10^5,a_i\le 2\times 10^6$，保证在任意时刻 $a$ 中的数均互不相同。

C++实现

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=2000004;
int res,n,m,a,tr[maxn]; 
void add(int p,int v){
	while(p<=maxn-2){
		tr[p]+=v;
		p+=p&-p;
	}
}
int sum(int p){
	int ret=0;
	while(p){
		ret+=tr[p];
		p-=p&-p;
	}
	return ret;
} 
signed main(){
	scanf("%lld %lld",&n,&m);
	for(int i=1;i<=n;i++){
		scanf("%lld",&a);
		res^=sum(maxn-2)-sum(a);
		add(a,1);
	}
	while(m--){
		int op,k,l1,r1,l2,r2,n1,n2,N,x;
		scanf("%lld",&op);
		if(op==1){
			scanf("%lld %lld %lld %lld",&l1,&r1,&l2,&r2);
			n1=r1-l1+1,n2=r2-l2+1,N=l2-r1-1;
			res^=N*(n1+n2)+n1*n2;
		}
		if(op==2){
			scanf("%lld %lld %lld",&l1,&r1,&k);
			n1=r1-l1+1,n2=k-r1;
			res^=n1*n2;
		}
		if(op==3){
			scanf("%lld",&x);
			res^=sum(maxn-2)-sum(x);
			add(x,1);
		}
		if(op==4){
			scanf("%d",&x);
			res^=sum(x);
			add(x,1);
		}
		puts(res&1?"odd":"even");
	}
	return 0;
}

后续

接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容