逆序对

我们称逆序对为一个序列中满足 $i<j$ 且 $a_i>a_j$ 的二元组 $(i,j)$ 。

若一个排列的逆序对个数为奇数，则称它为一个奇排列，否则它被称为偶排列。

给出一个长度为 $n$ 的排列，有 $4$ 种操作：

$1\ l\ r$ 交换 $a_l$ 和 $a_r$ 。
$2\ l\ r$ 翻转区间 $[l,r]$ 内的数。
$3\ l\ r\ k$ 将区间 $[l,r]$ 内的数左移 $k$ 位。
$4\ l\ r\ k$ 将区间 $[l,r]$ 内的数右移 $k$ 位。

对一个长度为 $n$ 的序列的操作定义如下：

翻转。对于所有 $1\leq i\leq n$ ，将第 $i$ 个位置的数移动到第 $n-i+1$ 个位置。
左移 $k$ 位。对于所有 $2\leq i\leq n$ ，将第 $i$ 个位置的数移动到第 $i-1$ 个位置，第 $1$ 个位置的数移动到第 $n$ 个位置。重复此操作 $k$ 次。
右移 $k$ 位。对于所有 $1\leq i<n$ ，将第 $i$ 个位置的数移动到第 $i+1$ 个位置，第 $n$ 个位置的数移动到第 $1$ 个位置。重复此操作 $k$ 次。

注意上述定义中同一个操作内的移动都是同时进行的。

小 $\mathcal T$ 想要知道每次操作之后这个排列是奇排列还是偶排列。

第一行两个整数 $n,m$ ，表示序列的长度和操作的次数。
第二行 $n$ 个整数，表示一个 $1$ 至 $n$ 的排列。
接下来 $m$ 行，每行三或四个整数，表示一次操作，具体格式及其含义见题目描述。

#include<bits/stdc++.h> #define N 1000005 using namespace std; int n,a[N],m,ans,t[N]; void add(int x){ for(;x<=n;x+=x&-x)t[x]^=1; } int sum(int x){ int res=0; for(;x;x-=x&-x)res^=t[x]; return res; } int main(){ cin>>n>>m; for(int i=1;i<=n;i++){ scanf("%d",&a[i]); } for(int i=n;i>=1;i--){ ans^=sum(a[i]); add(a[i]); } while(m--){ int op,l,r,k; scanf("%d%d%d",&op,&l,&r); if(op>2)scanf("%d",&k); if(op==1)ans^=1; else if(op==2)ans^=((r-l+1)/2)&1; else if(op>2)ans^=(k*(r-l+1-k))&1; cout<<ans<<"\n"; } }

详情