当前位置：首页 > news >正文

打卡信奥刷题（3235）用C++实现信奥题 P8449 [LSOT-1] 逆序对

news 2026/5/9 12:09:38

P8449 [LSOT-1] 逆序对

题目背景

逆序对真好玩

题目描述

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

区间交换；
把一个区间向后移动到第kkk个数字与第k+1k+1k+1个数字之间；
在最后插入一个数xxx；
在开头插入一个数xxx。

每个数数的序号为新序列重新从第一个数到第kkk个数编号为111到kkk。

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

输入格式

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

接下来一行输入nnn个正整数a1,a2,…,ana_1,a_2,\dots,a_na1,a2,…,an，表示初始序列。

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

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

输出格式

对于每一个指令执行后，如果逆序对数量是偶数，请输出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][1,1][1,1]和区间[2,2][2,2][2,2]交换，序列变为3 4 5 7 2 6。

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

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

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

【数据范围】

「本题采用捆绑测试」

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

对于100%100\%100%的数据，1≤n,m≤2×105,ai≤2×1061\le n,m \le 2\times 10^5,a_i\le 2\times10^61≤n,m≤2×105,ai≤2×106，保证在任意时刻aaa中的数均互不相同。

C++实现

#include<bits/stdc++.h>#defineintlonglongusingnamespacestd;constintmaxn=2000004;intres,n,m,a,tr[maxn];voidadd(intp,intv){while(p<=maxn-2){tr[p]+=v;p+=p&-p;}}intsum(intp){intret=0;while(p){ret+=tr[p];p-=p&-p;}returnret;}signedmain(){scanf("%lld %lld",&n,&m);for(inti=1;i<=n;i++){scanf("%lld",&a);res^=sum(maxn-2)-sum(a);add(a,1);}while(m--){intop,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");}return0;}