题目链接:戳我
60pts
有一点容易写错的小细节:
比如说求全局的段数的时候，如果只有一种颜色，那么当左右端点相等时，就不要ans--了。
注意右端点小于左端点的情况。
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#define MAXN 2010
using namespace std;
int n,m,q;
int c[MAXN],tmp[MAXN];
namespace subtask1
{
inline void solve()
{
while(q--)
{
int x,y,k;
char s[3];
scanf("%s",s);
if(s[0]=='R')
{
scanf("%d",&x);
x%=n;
for(int i=1;i<=n;i++)
{
if(i+x<=n) tmp[i+x]=c[i];
else tmp[i+x-n]=c[i];
}
for(int i=1;i<=n;i++) c[i]=tmp[i];
}
else if(s[0]=='F')
{
int l=2,r=n;
while(l<r)
{
swap(c[l],c[r]);
l++,r--;
}
}
else if(s[0]=='S')
{
scanf("%d%d",&x,&y);
swap(c[x],c[y]);
}
else if(s[0]=='P')
{
scanf("%d%d%d",&x,&y,&k);
if(y>=x)
{
for(int i=x;i<=y;i++) c[i]=k;
}
if(y<x)
{
for(int i=x;i<=n;i++) c[i]=k;
for(int i=1;i<=y;i++) c[i]=k;
}
}
else if(strlen(s)>1&&s[0]=='C'&&s[1]=='S')
{
scanf("%d%d",&x,&y);
int cur_ans=0,i=x;
if(y<x) y+=n;
while(i<=y)
{
cur_ans++;
while(i<y&&c[i]==c[i+1]) i++;
i++;
}
printf("%d\n",cur_ans);
}
else
{
int cur_ans=0,i=1;
while(i<=n)
{
cur_ans++;
while(i<n&&c[i]==c[i+1]) i++;
i++;
}
if(cur_ans>1&&c[n]==c[1]) cur_ans--;
printf("%d\n",cur_ans);
}
for(int i=1;i<=n;i++) c[i+n]=c[i];
}
}
}
using namespace subtask1;
int main()
{
#ifndef ONLINE_JUDGE
freopen("ce.in","r",stdin);
#endif
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) scanf("%d",&c[i]),c[i+n]=c[i];
scanf("%d",&q);
if(n<=1000&&q<=1000) subtask1::solve();
return 0;
}
100pts
如果没有翻转和旋转，很显然可以用线段树维护合并，更改和查询都是log的级别的。
但是旋转的话，我们可以通过记录一个变量，从而还原该操作在原先环中的位置。
然后观察翻转——通过绘图我们发现，翻转之后的环的顺时针移动翻转回来相当于原先的环的逆时针移动——所以我们就可以还原位置了。
我们把当前需要处理的位置，还原成它原本的位置上的编号，然后用线段树维护一下更新和查询就行了。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#define MAXN 500010
using namespace std;
int n,m,q,rev,kkk;
char s[5];
struct Node{int l,r,lc,rc,sum,tag;}t[MAXN<<2];
inline int ls(int x){return x<<1;}
inline int rs(int x){return x<<1|1;}
inline void push_up(int x)
{
t[x].lc=t[ls(x)].lc,t[x].rc=t[rs(x)].rc;
t[x].sum=t[ls(x)].sum+t[rs(x)].sum;
if(t[ls(x)].rc==t[rs(x)].lc) t[x].sum--;
}
inline void build(int x,int l,int r)
{
t[x].l=l,t[x].r=r;
if(l==r)
{
t[x].sum=1;
int cur;
scanf("%d",&cur);
t[x].lc=t[x].rc=cur;
return;
}
int mid=(l+r)>>1;
build(ls(x),l,mid);
build(rs(x),mid+1,r);
push_up(x);
}
inline void f(int x,int k)
{
t[x].lc=t[x].rc=t[x].tag=k;
t[x].sum=1;
}
inline void push_down(int x)
{
if(t[x].tag)
{
f(ls(x),t[x].tag);
f(rs(x),t[x].tag);
t[x].tag=0;
}
}
inline void update(int x,int ll,int rr,int k)
{
int l=t[x].l,r=t[x].r;
if(ll<=l&&r<=rr)
{
f(x,k);
return;
}
push_down(x);
int mid=(l+r)>>1;
if(ll<=mid) update(ls(x),ll,rr,k);
if(mid<rr) update(rs(x),ll,rr,k);
push_up(x);
}
inline int query(int x,int ll,int rr)
{
int l=t[x].l,r=t[x].r;
if(ll==l&&r==rr) return t[x].sum;
push_down(x);
int mid=(l+r)>>1;
if(rr<=mid) return query(ls(x),ll,rr);
if(ll>mid) return query(rs(x),ll,rr);
else
{
int cur_ans=query(ls(x),ll,mid)+query(rs(x),mid+1,rr);
if(t[ls(x)].rc==t[rs(x)].lc) cur_ans--;
return cur_ans;
}
}
inline int pos(int x)
{
if(rev) x=n-x+2;
kkk%=n;
x-=kkk;
if(x>n) x-=n;
if(x<1) x+=n;
return x;
}
inline int calc(int x,int l,int r,int k)
{
if(l==r) return t[x].lc;
push_down(x);
int mid=(l+r)>>1;
if(k<=mid) return calc(ls(x),l,mid,k);
else return calc(rs(x),mid+1,r,k);
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("ce.in","r",stdin);
#endif
scanf("%d%d",&n,&m);
build(1,1,n);
scanf("%d",&q);
while(q--)
{
int x,y,k;
scanf("%s",s);
if(s[0]=='R')
{
// printf("rotate\n");
scanf("%d",&x);
if(rev) kkk-=x;
else kkk+=x;
}
else if(s[0]=='F')
{
// printf("flip\n");
rev^=1;
}
else if(s[0]=='S')
{
// printf("swap\n");
scanf("%d%d",&x,&y);
x=pos(x),y=pos(y);
int c1=calc(1,1,n,x);
int c2=calc(1,1,n,y);
update(1,x,x,c2),update(1,y,y,c1);
}
else if(s[0]=='P')
{
// printf("paint\n");
scanf("%d%d%d",&x,&y,&k);
x=pos(x),y=pos(y);
if(rev) swap(x,y);
if(x<=y) update(1,x,y,k);
else update(1,x,n,k),update(1,1,y,k);
}
else if(strlen(s)>1&&s[0]=='C'&&s[1]=='S')
{
// printf("CS\n");
scanf("%d%d",&x,&y);
// printf("x=%d y=%d\n",x,y);
x=pos(x),y=pos(y);
// printf("x=%d y=%d\n",x,y);
if(rev) swap(x,y);
if(x<=y) printf("%d\n",query(1,x,y));
else
{
int cur_ans=query(1,x,n)+query(1,1,y);
if(t[1].rc==t[1].lc) cur_ans--;
printf("%d\n",cur_ans);
}
}
else
{
// printf("C\n");
int cur_ans=query(1,1,n);
if(cur_ans>1&&t[1].rc==t[1].lc) cur_ans--;
printf("%d\n",cur_ans);
}
}
return 0;
}