1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
| #include<iostream>
#define fin cin
#define fout cout
using namespace std;
const long MAX=500001;
struct node{
long lch,rch,left,right,reg,lcol,rcol,mid;
bool mark;
}tree[MAX*5];
long tot=1,delta=0,n,color[MAX],q,A,B,C,A1,B1,Count=0;
bool flip=true;
class regtree{
public:
inline void refresh(long index){
long lch=tree[index].lch,rch=tree[index].rch;
tree[index].lcol=tree[lch].lcol;
tree[index].rcol=tree[rch].rcol;
tree[index].reg=tree[lch].reg+tree[rch].reg-(tree[lch].rcol==tree[rch].lcol?1:0);
if(tree[index].reg==1) tree[index].mark=true;
else tree[index].mark=false;
}
void build(long left,long right,long index){
tree[index].left=left;
tree[index].right=right;
tree[index].mid=(left+right)/2;
tree[index].mark=false;
if(left<right){
tree[index].lch=++tot;
build(left,tree[index].mid,tot);
tree[index].rch=++tot;
build(tree[index].mid+1,right,tot);
refresh(index);
}else{
tree[index].lcol=tree[index].rcol=color[left];
tree[index].reg=1;
}
}
inline void downset(long index){
long lch=tree[index].lch,rch=tree[index].rch;
tree[lch].lcol=tree[rch].lcol=tree[lch].rcol=tree[rch].rcol=tree[index].lcol;
tree[lch].reg=1;
tree[rch].reg=1;
tree[lch].mark=tree[rch].mark=true;
tree[index].mark=false;
}
void paint(long left,long right,long col,long index){
if(!index) return;
if(tree[index].left>=left && tree[index].right<=right){
tree[index].lcol=tree[index].rcol=col;
tree[index].reg=1;
tree[index].mark=true;
}else{
if(tree[index].mark) downset(index);
if(left<=tree[index].mid) paint(left,right,col,tree[index].lch);
if(right>tree[index].mid) paint(left,right,col,tree[index].rch);
refresh(index);
}
}
long cseg(long left,long right,long index){
if(!index) return 0;
if(tree[index].left>=left && tree[index].right<=right){
return tree[index].reg;
}else{
long temp=0,key=0;
if(tree[index].mark) downset(index);
if(left<=tree[index].mid) {key++;temp+=cseg(left,right,tree[index].lch);}
if(right>tree[index].mid) {key++;temp+=cseg(left,right,tree[index].rch);}
return temp-((key==2 && tree[tree[index].lch].rcol==tree[tree[index].rch].lcol)?1:0);
}
}
long find(long pos,long index){
if(tree[index].left<=pos && pos<=tree[index].right && tree[index].reg==1){
return tree[index].lcol;
}else{
if(tree[index].mark) downset(index);
if(pos<=tree[index].mid && tree[index].lch) return find(pos,tree[index].lch);
else if(pos>tree[index].mid && tree[index].rch) return find(pos,tree[index].rch);
}
}
}line;
inline long hash(long pos){
if(!flip) pos=n-pos+2;
pos-=delta;
pos%=n;
pos=(pos+n)%n;
if(pos==0) pos=n;
return pos;
}
int main(){
fin>>n>>Count;
for(long i=1;i<=n;i++) fin>>color[i];
line.build(1,n,tot);
char op[3];
fin>>q;
for(long i1=1;i1<=q;i1++){
fin>>op;
if(op[0]=='R'){
fin>>A;
if(flip) delta+=A;
else delta-=A;
delta%=n;
}
else if(op[0]=='F') flip=!flip;
else if(op[0]=='S'){
fin>>A>>B;
A1=A;B1=B;
if(!flip){A=hash(B1);B=hash(A1);}
else {A=hash(A);B=hash(B);}
C=line.find(A,1);
Count=line.find(B,1);
line.paint(A,A,Count,1);
line.paint(B,B,C,1);
}
else if(op[0]=='P'){
fin>>A>>B>>C;
A1=A;B1=B;
if(!flip){A=hash(B1);B=hash(A1);}
else {A=hash(A);B=hash(B);}
if(A>B) {line.paint(A,n,C,1);line.paint(1,B,C,1);}
else line.paint(A,B,C,1);
}
else if(op[0]=='C'){
if(op[1]=='S'){
Count=0;
fin>>A>>B;
A1=A;B1=B;
if(!flip){A=hash(B1);B=hash(A1);}
else {A=hash(A);B=hash(B);}
if(A>B) {Count+=line.cseg(A,n,1);Count+=line.cseg(1,B,1);
if(tree[1].lcol==tree[1].rcol) Count--;}
else Count=line.cseg(A,B,1);
fout<<Count<<endl;
}else {if(tree[1].reg!=1)fout<<tree[1].reg-(tree[1].lcol==tree[1].rcol?1:0)<<endl;
else fout<<1<<endl;}
}
}
return 0;
}
|
