LibreOJ 2355 「NOI2007」项链工厂

首先,对于反转和轮转操作可以维护整体标记,只考虑其对下标的影响而不实际修改序列。
注意两者的顺序,我的代码选择了让反转标记的优先级高于轮转(当然反过来也没问题)。

然后考虑后四个操作。
考虑在线段树上维护三个信息:区间「部分」数,区间至左的颜色,区间至右的颜色。
合并时首先考虑直接把左右儿子的「部分」数加起来,然后考虑左儿子至右的颜色是否与右儿子至左的颜色相同。
如果满足,贡献要少一(因为可以合并)。

这道题更加让我想把「『SDOI2011』染色」给写出来,不能再偷懒了(

代码:

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
#include <cstdio>
#include <utility>
#include <algorithm>
#define ls (p << 1)
#define rs (ls | 1)
using namespace std;
const int N = 5e5;
int n,c,q,a[N + 5];
int rev,rot;
struct node
{
int cnt,lc,rc,tag;
} seg[(N << 2) + 10];
inline void push(int p)
{
if(~seg[p].tag)
{
seg[ls].cnt = 1,seg[ls].lc = seg[ls].rc = seg[ls].tag = seg[p].tag;
seg[rs].cnt = 1,seg[rs].lc = seg[rs].rc = seg[rs].tag = seg[p].tag;
seg[p].tag = -1;
}
}
void update(int l,int r,int k,int p,int tl,int tr)
{
if(l <= tl && tr <= r)
{
seg[p].cnt = 1,seg[p].lc = seg[p].rc = seg[p].tag = k;
return ;
}
push(p);
int mid = tl + tr >> 1;
l <= mid && (update(l,r,k,ls,tl,mid),1);
r > mid && (update(l,r,k,rs,mid + 1,tr),1);
seg[p].cnt = seg[ls].cnt + seg[rs].cnt - (seg[ls].rc == seg[rs].lc);
seg[p].lc = seg[ls].lc,seg[p].rc = seg[rs].rc;
}
pair< int,pair<int,int> > query(int l,int r,int p,int tl,int tr)
{
if(l <= tl && tr <= r)
return make_pair(seg[p].cnt,make_pair(seg[p].lc,seg[p].rc));
push(p);
int mid = tl + tr >> 1;
if(l <= mid && r > mid)
{
pair< int,pair<int,int> > left = query(l,r,ls,tl,mid);
pair< int,pair<int,int> > right = query(l,r,rs,mid + 1,tr);
return make_pair(left.first + right.first - (left.second.second == right.second.first),make_pair(left.second.first,right.second.second));
}
else if(l <= mid)
return query(l,r,ls,tl,mid);
else
return query(l,r,rs,mid + 1,tr);
}
int query(int x,int p,int tl,int tr)
{
if(tl == tr)
return seg[p].lc;
push(p);
int mid = tl + tr >> 1;
return x <= mid ? query(x,ls,tl,mid) : query(x,rs,mid + 1,tr);
}
inline int get(int x)
{
rev && (x = (n - x + 2) % n),x = (x - rot + n) % n,!x && (x = n);
return x;
}
inline void Rotate(int k)
{
k %= n,rev ? rot = (rot - k + n) % n : rot = (rot + k) % n;
}
inline void Flip()
{
rev ^= 1;
}
inline void Swap(int x,int y)
{
x = get(x),y = get(y);
int vx = query(x,1,1,n),vy = query(y,1,1,n);
update(x,x,vy,1,1,n),update(y,y,vx,1,1,n);
}
inline void Paint(int l,int r,int v)
{
l = get(l),r = get(r),rev && (swap(l,r),1);
if(l > r)
update(l,n,v,1,1,n),update(1,r,v,1,1,n);
else
update(l,r,v,1,1,n);
}
inline int Count()
{
int ret = seg[1].cnt;
ret = max(ret - (seg[1].lc == seg[1].rc),1);
return ret;
}
inline int CountSegment(int l,int r)
{
l = get(l),r = get(r),rev && (swap(l,r),1);
if(l > r)
return query(l,n,1,1,n).first + query(1,r,1,1,n).first - (seg[1].lc == seg[1].rc);
else
return query(l,r,1,1,n).first;
}
int main()
{
scanf("%d%d",&n,&c);
int x;
for(register int i = 1;i <= n;++i)
scanf("%d",&x),update(i,i,x,1,1,n);
scanf("%d",&q);
char op[5];
int l,r;
for(;q;--q)
{
scanf("%s",op + 1);
if(op[1] == 'R')
scanf("%d",&x),Rotate(x);
else if(op[1] == 'F')
Flip();
else if(op[1] == 'S')
scanf("%d%d",&l,&r),Swap(l,r);
else if(op[1] == 'P')
scanf("%d%d%d",&l,&r,&x),Paint(l,r,x);
else if(op[1] == 'C' && op[2] == 'S')
scanf("%d%d",&l,&r),printf("%d\n",CountSegment(l,r));
else
printf("%d\n",Count());
}
}