Description

　　T 公司是一家专门生产彩色珠子项链的公司，其生产的项链设计新颖、款式多样、价格适中，广受青年人的喜爱。最近T 公司打算推出一款项链自助生产系统，使用该系统顾客可以自行设计心目中的美丽项链。
　　该项链自助生产系统包括硬件系统与软件系统，软件系统与用户进行交互并控制硬件系统，硬件系统接受软件系统的命令生产指定的项链。该系统的硬件系统已经完成，而软件系统尚未开发，T 公司的人找到了正在参加全国信息学竞赛的你，你能帮助T 公司编写一个软件模拟系统吗？
　　一条项链包含N 个珠子，每个珠子的颜色是1, 2, …, c 中的一种。项链被固定在一个平板上，平板的某个位置被标记位置1，按顺时针方向其他位置被记为2,3,…,N。 　　
　　你将要编写的软件系统应支持如下命令：
　　1.R k(0 < K < N) 意为Rotate k。将项链在平板上顺时针旋转k 个位置, 即原来处于位置1 的珠子将转至位置k+1，处于位置2 的珠子将转至位置k+2，依次类推。
　　2. F 意为Flip。将平板沿着给定的对称轴翻转，原来处于位置1 的珠子不动，位置2 上的珠子与位置N 上的珠子互换，位置3 上的珠子与位置N-1 上的珠子互换，依次类推。
　　3.S i j(1≤I,j≤N) 意为Swap i , j。将位置i 上的珠子与位置j 上的珠子互换。
　　4.P I j x(1≤I,j≤N,x≤c) 意为Paint i , j , x。将位置i 沿顺时针方向到位置j 的一段染为颜色x。
　　5.C 意为Count。查询当前的项链由多少个“部分”组成，我们称项链中颜色相同的一段为一个“部分”。
　　6.CS i j(1≤I,j≤N) 意为CountSegment i , j。查询从位置i沿顺时针方向到位置j 的一段中有多少个部分组成。

Input

　　输入文件第一行包含两个整数N, c，分别表示项链包含的珠子数目以及颜色数目。
第二行包含N 个整数，x1, x2…, xn，表示从位置1 到位置N 的珠子的颜色，1 ≤ xi ≤ c。
第三行包含一个整数Q，表示命令数目。
接下来的Q 行每行一条命令，如上文所述。

Output

　　对于每一个C 和CS 命令，应输出一个整数代表相应的答案。

Sample Input

5 3
1 2 3 2 1
4
C
R 2
P 5 5 2
CS 4 1

Sample Output

4
1

Data Constraint

Hint

【数据规模和约定】
　　对于60%的数据，N ≤ 1 000，Q ≤ 1 000；
　　对于100%的数据，N ≤ 500 000，Q ≤ 500 000，c ≤ 1 000。

 

题解

• 主要是翻转和旋转操作比较奇怪，其他都是线段树基本操作
• 一个是顺时针旋转，如果不存在翻转操作
• 我们显然可以通过记录顺时针旋转的次数来还原当前的一号位置
• 多了一个翻转
• 仔细观察，就是把顺时针变为了逆时针而已
• 所以直接乘个负号，额外加一个标记就行了

代码

1 #include <cstdio> 2 #include <iostream> 3 #include <cstring> 4 using namespace std; 5 bool rev; 6 char ch[5]; 7 int n,m,p; 8 struct data{int l,r,sum;}; 9 struct tree{int l,r,tag;data v;}t[2000005]; 10 data merge(data a,data b) 11 { 12 data r={a.l,b.r,a.sum+b.sum}; 13 if (a.r==b.l) r.sum--; 14 return r; 15 } 16 void calc(int &x,int &y) 17 { 18 if (rev) x=(n*2+2-p-x)%n,y=(n*2+2-p-y)%n,swap(x,y); 19 else x=(x-p+n)%n,y=(y-p+n)%n; 20 if (x==0) x=n; 21 if (y==0) y=n; 22 } 23 void pushdown(int d) 24 { 25 if (!t[d].tag||t[d].l==t[d].r) return; 26 int r=t[d].tag; t[d].tag=0; 27 t[d*2].tag=t[d*2+1].tag=t[d*2].v.l=t[d*2+1].v.l=t[d*2].v.r=t[d*2+1].v.r=r; 28 t[d*2].v.sum=t[d*2+1].v.sum=1; 29 } 30 void build(int d,int l,int r) 31 { 32 t[d].l=l,t[d].r=r; 33 if (l==r) 34 { 35 scanf("%d",&t[d].v.l),t[d].v.r=t[d].v.l,t[d].v.sum=1; 36 return; 37 } 38 int mid=l+r>>1; 39 build(d*2,l,mid),build(d*2+1,mid+1,r),t[d].v=merge(t[d*2].v,t[d*2+1].v); 40 } 41 data query(int d,int l,int r) 42 { 43 pushdown(d); 44 int L=t[d].l,R=t[d].r; 45 if (l==L&&r==R) return t[d].v; 46 int mid=L+R>>1; 47 if (r<=mid) return query(d*2,l,r); else if (l>mid) return query(d*2+1,l,r); else return merge(query(d*2,l,mid),query(d*2+1,mid+1,r)); 48 } 49 void modify(int d,int l,int r,int x) 50 { 51 pushdown(d); 52 int L=t[d].l,R=t[d].r; 53 if (l==L&&R==r) 54 { 55 t[d].v.l=t[d].v.r=t[d].tag=x,t[d].v.sum=1; 56 return; 57 } 58 int mid=L+R>>1; 59 if (r<=mid) modify(d*2,l,r,x); else if (l>mid) modify(d*2+1,l,r,x); else modify(d*2,l,mid,x),modify(d*2+1,mid+1,r,x); 60 t[d].v=merge(t[d*2].v,t[d*2+1].v); 61 } 62 int main() 63 { 64 freopen("data.in","r",stdin); 65 scanf("%d%d",&n,&m),build(1,1,n),scanf("%d",&m); 66 for (int x,y,z;m;m--) 67 { 68 scanf("%s",ch); 69 if (ch[0]=='R') 70 { 71 scanf("%d",&x); 72 if (rev) p=(p+n-x)%n; else p=(p+x)%n; 73 } 74 if (ch[0]=='F') rev^=1; 75 if (ch[0]=='S') 76 { 77 int a,b; data ans; 78 scanf("%d%d",&x,&y),calc(x,y); 79 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; 80 modify(1,x,x,b),modify(1,y,y,a); 81 } 82 if (ch[0]=='P') 83 { 84 scanf("%d%d%d",&x,&y,&z),calc(x,y); 85 if (x<=y) modify(1,x,y,z); else modify(1,x,n,z),modify(1,1,y,z); 86 } 87 if (ch[0]=='C'&&ch[1]=='S') 88 { 89 scanf("%d%d",&x,&y),calc(x,y); data ans; 90 if (x<=y) ans=query(1,x,y); else ans=merge(query(1,x,n),query(1,1,y)); 91 printf("%d\n",ans.sum); 92 } 93 if (ch[0]=='C'&&ch[1]!='S') 94 { 95 data ans=query(1,1,n); 96 int r=ans.sum; 97 if (ans.l==ans.r) r=max(r-1,1); 98 printf("%d\n",r); 99 } 100 } 101 }

 

转载于:https://www.cnblogs.com/Comfortable/p/11142764.html

总结

以上是生活随笔为你收集整理的[线段树] Jzoj P1214 项链工厂的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。