【Bzoj1858】【Luogu2572】序列操作

来源和评测点

SCOI2010
Bzoj1858
Luogu2572

题目

【题目大意】
lxhgww最近收到了一个01序列,序列里面包含了n个数,
这些数要么是0,要么是1,现在对于这个序列有五种变换操作和询问操作:
0 a b 把[a,b]区间内的所有数全变成0
1 a b 把[a,b]区间内的所有数全变成1
2 a b 把[a,b]区间内的所有数全部取反,也就是说把所有的0变成1,把所有的1变成0
3 a b 询问[a,b]区间内总共有多少个1
4 a b 询问[a,b]区间内最多有多少个连续的1
对于每一种询问操作,lxhgww都需要给出回答,聪明的程序员们,你们能帮助他吗?
【输入格式】
输入数据第一行包括2个数,n和m,分别表示序列的长度和操作数目
第二行包括n个数,表示序列的初始状态
接下来m行,每行3个数,op, a, b,(0<=op<=4,0<=a<=b<n)表示对于区间[a, b]执行标号为op的操作
【输出格式】
对于每一个询问操作,输出一行,包括1个数,表示其对应的答案
【输入样例】
10 10
0 0 0 1 1 0 1 0 1 1
1 0 2
3 0 5
2 2 2
4 0 4
0 3 6
2 3 7
4 2 8
1 0 5
0 5 6
3 3 9
【输出样例】
5
2
6
5

分析

本题最重要的只有一点,相通了这个,再注意一下细节就好了。
这也是难点:如何解决最长连续的问题呢?
考虑用线段树维护区间信息:lmx,rmx,mx,sum
lmx和rmx用于在区间合并的时候更新mx,保证正确性。
然后就是一些细节问题了,例如标记的传递与先后处理顺序。

最后提醒一句,因为本人老是忘记:反转标记是用xor来修改的
还有就是我居然忘记要双倍空间了……

代码

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
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
//Zory-2018
//*******************头文件*******************
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int mymax(int x,int y) {return x>y?x:y;}
//*******************全局常量*******************
const int MAXN=210000;//debug
//*******************全局定义*******************
struct info
{
int sum;//个数
int lmx,rmx;//边缘最长连续,合并用
int mx;//最长连续
int all;//长度
info()
{
lmx=mx=rmx=0;
sum=all=0;
}
};
struct seg
{
int l,r,mid;
int lc,rc;
bool tg1,tg1n,tg2;
info f[2];
}p[MAXN];
//*******************info*******************
info merg(info a,info b)
{
info c;
c.sum=a.sum+b.sum;c.all=a.all+b.all;
c.lmx=a.lmx;if(c.lmx==a.all) c.lmx+=b.lmx;
c.rmx=b.rmx;if(c.rmx==b.all) c.rmx+=a.rmx;
c.mx=mymax(a.mx,b.mx);c.mx=mymax(c.mx,a.rmx+b.lmx);
return c;
}
void setall(info &a)
{
a.mx=a.lmx=a.rmx=a.sum=a.all;
}
void setno(info &a)
{
a.mx=a.lmx=a.rmx=a.sum=0;
}
//*******************接口*******************
void update(int x)
{
int lc=p[x].lc,rc=p[x].rc;
if(p[x].tg1)
{
p[x].tg1=0;
bool b=p[x].tg1n;
setall(p[x].f[b]);
setno(p[x].f[!b]);
p[lc].tg1=p[rc].tg1=1;
p[lc].tg1n=p[rc].tg1n=b;
p[lc].tg2=p[rc].tg2=0;
}
if(p[x].tg2)
{
p[x].tg2=0;
swap(p[x].f[0],p[x].f[1]);
update(lc);update(rc);//确保不冲突
p[lc].tg2^=1;p[rc].tg2^=1;//debug,总是忘记
}
}
int cnt;
bool cl[MAXN];
int build(int l,int r)
{
int t=++cnt;
p[t].l=l;p[t].r=r;
if(l<r)
{
p[t].mid=(l+r)/2;
p[t].lc=build(l,p[t].mid);
p[t].rc=build(p[t].mid+1,r);
p[t].f[0]=merg(p[p[t].lc].f[0],p[p[t].rc].f[0]);
p[t].f[1]=merg(p[p[t].lc].f[1],p[p[t].rc].f[1]);
}
else
{
bool b=cl[l];
p[t].f[0].all=p[t].f[1].all=1;
setall(p[t].f[b]);setno(p[t].f[!b]);
}
p[t].tg1=p[t].tg2=0;
return t;
}
void change(int x,int l,int r,bool b)
{
if(p[x].l==l and p[x].r==r)
{
p[x].tg1=1;
p[x].tg1n=b;
p[x].tg2=0;
return;
}
update(x);
int lc=p[x].lc,rc=p[x].rc,mid=(p[x].l+p[x].r)/2;
if(r<=mid) change(lc,l,r,b);
else if(l>mid) change(rc,l,r,b);
else change(lc,l,mid,b),change(rc,mid+1,r,b);
update(lc);update(rc);//debug
p[x].f[0]=merg(p[lc].f[0],p[rc].f[0]);
p[x].f[1]=merg(p[lc].f[1],p[rc].f[1]);
}
void opposite(int x,int l,int r)
{
update(x);
if(p[x].l==l and p[x].r==r)
{
p[x].tg2=1;
return;
}
int lc=p[x].lc,rc=p[x].rc,mid=(p[x].l+p[x].r)/2;
if(r<=mid) opposite(lc,l,r);
else if(l>mid) opposite(rc,l,r);
else opposite(lc,l,mid),opposite(rc,mid+1,r);
update(lc);update(rc);//debug
p[x].f[0]=merg(p[lc].f[0],p[rc].f[0]);
p[x].f[1]=merg(p[lc].f[1],p[rc].f[1]);
}
info ask(int x,int l,int r)
{
update(x);
if(p[x].l==l and p[x].r==r) return p[x].f[1];
int lc=p[x].lc,rc=p[x].rc,mid=(p[x].l+p[x].r)/2;
if(r<=mid) return ask(lc,l,r);
if(l>mid) return ask(rc,l,r);
return merg( ask(lc,l,mid),ask(rc,mid+1,r) );
}
//*******************主函数*******************
int main()
{
int n,m;scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) scanf("%d",&cl[i]);
cnt=0;build(1,n);
while(m--)
{
int op,a,b;scanf("%d%d%d",&op,&a,&b);
a++;b++;
if(op==0) change(1,a,b,0);
if(op==1) change(1,a,b,1);
if(op==2) opposite(1,a,b);
if(op==3)
{
info t=ask(1,a,b);
printf("%d\n",t.sum);
}
if(op==4)
{
info t=ask(1,a,b);
printf("%d\n",t.mx);
}
}
}

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.ink/posts/cf34.html
转载请注明出处,谢谢!