自动搬运

查看原文

来自洛谷，原作者为

	Jμdge 这个家伙很懒，而且很菜

搬运于2025-08-24 21:56:48，当前版本为作者最后更新于2018-11-08 22:18:14，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

我去，这题居然没人写ODT？ 虽说ODT跑的确实慢...（最后一个点卡时过，960ms+，所以可能要卡点常吧）

于是贡献一发ODT。

本来想了很久的标记处理（就是顺时针转以及翻转）

后来想不出来，本来想弃坑跳线段树的，然后想了想借(co)鉴(py)一下网上的标记处理不就行了？线段树操作用珂朵莉带一带，秒解。然后又肝了很久珂朵莉。

最后还是肝出来了，就是两个小细节注意一下就好了。其他地方没什么亮点，都是珂朵莉基操。

标记处理以及修改的边界维护全是抄的QvQ

//by Judge
#include<set>
#include<cstdio>
#include<iostream>
#define IT set<node>::iterator
using namespace std;
const int M=2e5+5;
inline int read(){ int x=0,f=1; char c=getchar();
	for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;
	for(;isdigit(c);c=getchar()) x=x*10+c-'0'; return x*f;
} inline int cread(){ char c=getchar(); static int x;
	while(!isupper(c)) c=getchar();
	switch(c){
		case 'R': x=1; break;
		case 'F': x=2; break;
		case 'S': x=3; break;
		case 'P': x=4; break;
		case 'C': x=5; break;
	} c=getchar(); if(isupper(c)) x=6; return x;
} char sr[1<<21],z[20];int C=-1,Z;
inline void Ot(){fwrite(sr,1,C+1,stdout),C=-1;}
inline void print(int x,char chr='\n'){
    if(C>1<<20)Ot();if(x<0)sr[++C]=45,x=-x;
    while(z[++Z]=x%10+48,x/=10);
    while(sr[++C]=z[Z],--Z);sr[++C]=chr;
}
inline void cmax(int& a,int b) { if(a<b) a=b; }
struct node { int l,r; mutable int v; //都是基操
	node(int l,int r=-1,int v=0):l(l),r(r),v(v){} node() {}
	bool operator < (const node& b) const { return l<b.l; }
}; set<node> s; IT it,lit,rit; int n,m,mov,rev;
inline IT split(int pos) { //都是基操
	it=s.lower_bound(node(pos));
	if(it!=s.end()&&it->l==pos) return it;
	--it; int l=it->l,r=it->r,v=it->v;
	s.erase(it),s.insert(node(l,pos-1,v));
	return s.insert(node(pos,r,v)).first;
}
inline void update(int l,int r,int v) { //都是基操
	rit=split(r+1),lit=split(l);
	s.erase(lit,rit),s.insert(node(l,r,v));
}
inline int query(int l,int r) { //人类的本质竟然是____
	int res=0,las=0;
	rit=split(r+1),lit=split(l);
	for(; lit!=rit; las=lit->v,++lit)
		res+=lit->v!=las;
	return res;
}
inline int col(int x) { //这里直接split
	return it=split(x),it->v;
}
inline int chg(int x) { //借(chao)来的
	if(rev) x=n-x+2;
	x-=mov;
	for(; x>n; x-=n);
	for(; x<1; x+=n);
	return x;
}
int main() {
	n=read(),m=read();
	for(int i=1,x; i<=n; ++i)
		x=read(),s.insert(node(i,i,x));
	int op,l,r,k,a,b,ans;
	for(int i=1,m=read(); i<=m; ++i) {
		op=cread();
		if(op==1) {
			k=read();
			mov+=(rev)?(-k):k;
			for(; mov>n; mov-=n);
			for(; mov<0; mov+=n);
		} else if(op==2) rev^=1;
		else if(op==3) {
			l=read(),r=read();
			l=chg(l),r=chg(r);
			a=col(l),b=col(r);
			update(l,l,b);
			update(r,r,a);
		} else if(op==4) {
			l=read(),r=read(),k=read();
			l=chg(l),r=chg(r);
			if(rev) swap(l,r);
			if(l<=r) update(l,r,k);
			else update(l,n,k),update(1,r,k);
		} else if(op==5) {
			ans=query(1,n);
			if(ans>1) ans-=col(1)==col(n); //这里要特判啊
			print(ans);
		} else if(op==6) {
			l=read(),r=read();
			l=chg(l),r=chg(r);
			if(rev) swap(l,r);
			if(l<=r) ans=query(l,r);
			else {
				ans=query(l,n)+query(1,r);
				if(ans>1) ans-=col(1)==col(n); //这里也是
			}
			print(ans);
		}
	} return Ot(),0;
}