P8449 [LSOT-1] 逆序对题目背景逆序对真好玩题目描述你需要维护一个数列支持以下444种操作区间交换把一个区间向后移动到第kkk个数字与第k1k1k1个数字之间在最后插入一个数xxx在开头插入一个数xxx。每个数数的序号为新序列重新从第一个数到第kkk个数编号为111到kkk。现在每次操作过后请你输出整个数列逆序对数量的奇偶性。输入格式第一行输入两个正整数n,mn,mn,m表示初始序列的长度与操作个数。接下来一行输入nnn个正整数a1,a2,…,ana_1,a_2,\dots,a_na1​,a2​,…,an​表示初始序列。接下来mmm行每行先输入一个ttt表示操作编号之后若t1t1t1则输入四个正整数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≤r1l2≤r2l_1\le r_1 l_2\le r_2l1​≤r1​l2​≤r2​若t2t2t2则输入三个正整数l,r,kl,r,kl,r,k表示将区间[l,r][l,r][l,r]移动至序列的第kkk个数与第k1k1k1个数之间保证rkrkrk若t3t3t3则输入一个正整数xxx表示将xxx插入到序列末端若t4t4t4则输入一个正整数xxx表示将xxx插入到序列首端。输出格式对于每一个指令执行后如果逆序对数量是偶数请输出even否则输出odd。输入输出样例 #1输入 #16 4 4 3 5 7 2 6 1 1 1 2 2 2 1 1 3 3 11 4 1输出 #1odd 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≤102Subtask 2(15 pts): n,m≤103\texttt{Subtask 2(15 pts): }n,m\le 10^3Subtask 2(15 pts):n,m≤103Subtask 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实现#includebits/stdc.h#defineintlonglongusingnamespacestd;constintmaxn2000004;intres,n,m,a,tr[maxn];voidadd(intp,intv){while(pmaxn-2){tr[p]v;pp-p;}}intsum(intp){intret0;while(p){rettr[p];p-p-p;}returnret;}signedmain(){scanf(%lld %lld,n,m);for(inti1;in;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(op1){scanf(%lld %lld %lld %lld,l1,r1,l2,r2);n1r1-l11,n2r2-l21,Nl2-r1-1;res^N*(n1n2)n1*n2;}if(op2){scanf(%lld %lld %lld,l1,r1,k);n1r1-l11,n2k-r1;res^n1*n2;}if(op3){scanf(%lld,x);res^sum(maxn-2)-sum(x);add(x,1);}if(op4){scanf(%d,x);res^sum(x);add(x,1);}puts(res1?odd:even);}return0;}后续接下来我会不断用C来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现记录日常的编程生活、比赛心得感兴趣的请关注我后续将继续分享相关内容