【BZOJ 1493】[NOI2007]项练工厂
1493: [NOI2007]项链工厂
Time Limit: 30 Sec Memory Limit: 64 MBSubmit: 992 Solved: 454
[Submit][Status]
Description
Input
输入文件第一行包含两个整数N, c，分别表示项链包含的珠子数目以及颜色 数目。第二行包含N 个整数，x1, x2…, xn，表示从位置1 到位置N 的珠子的颜色， 1 ≤ xi ≤ c。第三行包含一个整数Q，表示命令数目。接下来的Q 行每行一条命令， 如上文所述。
Output
对于每一个C 和CS 命令，应输出一个整数代表相应的答案。
Sample Input
1 2 3 2 1
4
C
R 2
P 5 5 2
CS 4 1
Sample Output
1
HINT
对于60%的数据，N ≤ 1 000，Q ≤ 1 000； 对于100%的数据，N
≤ 500 000，Q ≤ 500 000，c ≤ 1 000。
Source
Splay
线段树。
这道题如果没有旋转翻转操作的话就是一道区间修改，区间查询的线段树水题。
那么对于R,F操作应该怎么处理呢？
通过画图可以发现R,F操作之后珠子的位置改变了，但是珠子的相对位置没变（相对位置通俗来说就是一个珠子左右两边的珠子还是原来那两个）
所以对于R,F操作我们只需要分别记录两个量即可：mov,rev
1.mov:表示当前整体顺时针移动了mov（即k变成k+mov）
输入R k，分两种情况：
没有被翻转过，mov+=k；
被翻转过，mov-=k
2.rev:表示当前是否被翻转过
输入F,直接rev^=1
有了mov和rev之后，每次读入一个位置，把这个位置转换成最初他所在的位置，然后再在线段树上进行修改，查询即可。(见代码中change(x))
注意：
1.每次修改或查询子树之前要下传标记，修改子树之后要上传标记。
2.push_down,push_up操作中对于没有子树的结点要特判。
3.push_up中要记得修改lc（最左端颜色）,rc（最右端颜色）的值
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <string>
#include <cstring>
#define N 500005
using namespace std;
int rev=0,mov=0;
int n,cnt,c[N];
struct segtree
{
int modi,lc,rc,cs,l,r; //分别表示被修改成的数，最左端颜色，最右端颜色，当前区间有几个部分，左儿子，右儿子
}a[N*3];
void change(int &a)
{
if (rev) a=n-a+2;
a-=mov;
while (a<1) a+=n;
while (a>n) a-=n;
}
void push_down(int x)
{
if (a[x].modi)
{
a[x].lc=a[x].rc=a[a[x].l].modi=a[a[x].r].modi=a[x].modi;
if (a[x].l==0||a[x].r==0) a[0].modi=0;
a[x].cs=1;
a[x].modi=0;
}
}
void push_up(int x)
{
if (!x) return;
push_down(a[x].l);push_down(a[x].r);
a[x].cs=a[a[x].l].cs+a[a[x].r].cs;
if (a[x].cs>1&&a[a[x].l].rc==a[a[x].r].lc)
a[x].cs--;
if (a[x].l) a[x].lc=a[a[x].l].lc;
if (a[x].r) a[x].rc=a[a[x].r].rc;
}
void build(int x,int l,int r)
{
if (l>r) return;
a[x].lc=c[l],a[x].rc=c[r];
a[x].l=a[x].r=0;
a[x].modi=0;
if (l==r)
{
a[x].cs=1;
return;
}
int m=(l+r)>>1;
build(x<<1,l,m);
build(x<<1|1,m+1,r);
if (l<=m) a[x].l=x<<1;
if (m+1<=r) a[x].r=x<<1|1;
push_up(x);
}
int getcolor(int x,int l,int r,int p)
{
push_down(x);
if (l==r&&l==p) return a[x].lc;
int m=(l+r)>>1;
if (p<=m) return getcolor(a[x].l,l,m,p);
else return getcolor(a[x].r,m+1,r,p);
}
void paint(int x,int lx,int rx,int l,int r,int c)
{
push_down(x);
if (l<=lx&&r>=rx)
{
a[x].modi=c;
return;
}
int m=(lx+rx)>>1;
if (l<=m) paint(a[x].l,lx,m,l,r,c);
if (r>m) paint(a[x].r,m+1,rx,l,r,c);
push_up(x);
}
int count(int x,int lx,int rx,int l,int r)
{
push_down(x);
if (l==lx&&r==rx) return a[x].cs;
int m=(lx+rx)>>1,ans=0;
if (r<=m) ans=count(a[x].l,lx,m,l,r);
else
{
if(l>m) ans=count(a[x].r,m+1,rx,l,r);
else
{
int o=0;
ans=count(a[x].l,lx,m,l,m)+count(a[x].r,m+1,rx,m+1,r);
if (a[a[x].l].rc==a[a[x].r].lc) o=1;
ans-=o;
if (ans<=0) ans=1;
}
}
return ans;
}
int main()
{
scanf("%d%d",&n,&cnt);
for (int i=1;i<=n;i++)
scanf("%d",&c[i]);
build(1,1,n);
int q;
scanf("%d",&q);
while (q--)
{
char str[10];
scanf("%s",str);
int k,x,y,xx,yy,g,ans;
switch(str[0])
{
case 'R':
scanf("%d",&k);
if (rev) mov-=k;
else mov+=k;
while (mov<0) mov+=n;
while (mov>n) mov-=n;
break;
case 'F':
rev^=1;
break;
case 'S':
scanf("%d%d",&x,&y);
change(x),change(y);
xx=getcolor(1,1,n,x),yy=getcolor(1,1,n,y);
paint(1,1,n,x,x,yy);
paint(1,1,n,y,y,xx);
break;
case 'P':
scanf("%d%d%d",&x,&y,&g);
change(x),change(y);
if (rev) swap(x,y);
if (x>y) paint(1,1,n,x,n,g),paint(1,1,n,1,y,g);
else paint(1,1,n,x,y,g);
break;
case 'C':
if (strlen(str)>1)
{
scanf("%d%d",&x,&y);
change(x),change(y);
if (rev) swap(x,y);
if (x<=y)
{
ans=count(1,1,n,x,y);
if (x==1&&y==n&&ans>1&&a[1].lc==a[1].rc) ans--;
}
else
{
ans=count(1,1,n,x,n)+count(1,1,n,1,y);
if (a[1].lc==a[1].rc) ans--;
}
}
else
{
ans=a[1].cs;
if (ans>1&&a[1].lc==a[1].rc) ans--;
}
printf("%d\n",ans);
break;
}
}
return 0;
}
感悟：
1.过了样例一激动就交了，然后就CE了：头文件没写全。。
2.wa:是因为Push_up操作没写全，对于没有左右儿子的结点没有特殊处理
3.RE:线段树数组只开到了n*2，按理说是够了，但为什么会RE??
4.对于R,F操作的处理要抓住相对位置不变这一关键，就可以用线段树来做了；mov和rev要多加思考。。