C++11(clang++ 3.9) 解法, 执行用时: 627ms, 内存消耗: 25764K, 提交时间: 2019-01-07 17:07:55

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#include<cmath>
#define inf 0x7fffffff
#define ll long long
using namespace std;
inline int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
bool rev;
int n,m,delta;
struct data{int l,r,sum;};
struct seg{int l,r,tag;data c;}t[2000005];
void cal(int &x,int &y)
{
 if(rev)
 {
  x=(n+n+2-delta-x)%n;
  y=(n+n+2-delta-y)%n;
  swap(x,y);
 }
 else 
 {
  x=(x-delta+n)%n;
     y=(y-delta+n)%n;
 }
 if(x==0)x=n;if(y==0)y=n;
}
data merge(data a,data b)
{
 data tmp;
 tmp.l=a.l;tmp.r=b.r;
 tmp.sum=a.sum+b.sum;
 if(a.r==b.l)tmp.sum--;
 return tmp;
}
void update(int k)
{
 t[k].c=merge(t[k<<1].c,t[k<<1|1].c);
}
void pushdown(int k)
{
 if(!t[k].tag||t[k].l==t[k].r)return;
 int tag=t[k].tag;t[k].tag=0;
 t[k<<1].tag=t[k<<1|1].tag=tag;
 t[k<<1].c.l=t[k<<1|1].c.l=tag;
 t[k<<1].c.r=t[k<<1|1].c.r=tag;
 t[k<<1].c.sum=t[k<<1|1].c.sum=1;
}
void build(int k,int l,int r)
{
 t[k].l=l;t[k].r=r;
 if(l==r)
 {
     t[k].c.l=t[k].c.r=read();
  t[k].c.sum=1;
  return;
 }
 int mid=(l+r)>>1;
 build(k<<1,l,mid);build(k<<1|1,mid+1,r);
 update(k);
}
data query(int k,int x,int y)
{
 pushdown(k);
 int l=t[k].l,r=t[k].r;
 if(l==x&&y==r)return t[k].c;
 int mid=(l+r)>>1;
 if(y<=mid)return query(k<<1,x,y);
 else if(x>mid)return query(k<<1|1,x,y);
 else
 {
  return merge(query(k<<1,x,mid),query(k<<1|1,mid+1,y));
 }
}
void modify(int k,int x,int y,int val)
{
 pushdown(k);
 int l=t[k].l,r=t[k].r;
 if(l==x&&y==r)
 {
  t[k].c.l=t[k].c.r=t[k].tag=val;
  t[k].c.sum=1;
  return;
 }
 int mid=(l+r)>>1;
 if(y<=mid)modify(k<<1,x,y,val);
 else if(x>mid)modify(k<<1|1,x,y,val);
 else 
 {
  modify(k<<1,x,mid,val);
  modify(k<<1|1,mid+1,y,val);
 }
 update(k);
}
int main()
{
 n=read();m=read();
 build(1,1,n);
 char ch[5];
 m=read();
 int x,y,val;
 for(int i=1;i<=m;i++)
 {
  scanf("%s",ch);
  if(ch[0]=='R')
  {
   x=read();
   if(rev)delta=(delta+n-x)%n;
   else delta=(delta+x)%n;
  }
  if(ch[0]=='F')rev^=1;
  if(ch[0]=='S')
  {
   x=read();y=read();
   int a,b;
      cal(x,y);data ans;
   if(x>y)
   {
    ans=query(1,y,x);
    a=ans.r;b=ans.l;
   }
   else 
   {
    ans=query(1,x,y);
    a=ans.l;b=ans.r;
   }
   modify(1,x,x,b);modify(1,y,y,a);
  }
  if(ch[0]=='P')
  {
   x=read();y=read();val=read();
      cal(x,y);
   if(x<=y)modify(1,x,y,val);
   else 
   {
    modify(1,x,n,val);modify(1,1,y,val);
   }
  }
     if(ch[0]=='C'&&ch[1]=='S')
  {
   x=read();y=read();
      cal(x,y);
   data ans;
   if(x<=y)ans=query(1,x,y);
   else 
    ans=merge(query(1,x,n),query(1,1,y));
   printf("%d\n",ans.sum);
  }
  if(ch[0]=='C'&&ch[1]!='S')
  {
   data ans=query(1,1,n);
   int tmp=ans.sum;
   if(ans.l==ans.r)
    tmp=max(tmp-1,1);
   printf("%d\n",tmp);
  }
 }
 return 0;
}