Reincarnation

正因为梦易碎，才格外美好。

P2572 [SCOI2010] 序列操作

发表于 分类于
本文字数： 6.1k 阅读时长 ≈ 6 分钟

“复建ing”

题目简介

题目名称：序列操作
题目来源：四川省选

评测链接：https://www.luogu.com.cn/problem/P2572

形式化题意：给定一个 序列，共有 个操作：

  • 将区间 全部变为 ；
  • 将区间 取反，也就是全部异或上 ；
  • 询问区间 中有多少个 ；
  • 询问区间 中最长的 的连续区间长度。

数据范围：

前三个操作都比较好实现，可以直接记录 即可，而对于最后一个操作，我们可以像维护最大子段和那样维护 ，即包含左右段点的最大值和段间最大值，这样的话，我们需要维护 个变量（ 各 个）即 就能解决这个问题。

主要是注意 pushdown 的顺序，因为覆盖的优先级应当高于取反，正因如此，在处理覆盖的下传时同样需要将取反清空。

以及不知道为什么在处理答案的时候居然还需要 pushdown。

AC Code
 
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
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
// ----- Eternally question-----
// Problem: P2572 [SCOI2010] 序列操作
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P2572
// Memory Limit: 128 MB
// Time Limit: 1000 ms
// Written by: Eternity
// Time: 2023-06-25 21:07:27
// ----- Endless solution-------

#include<bits/stdc++.h>
#define re register
typedef long long ll;
template<class T>
inline void read(T &x)
{
	x=0;
	char ch=getchar(),t=0;
	while(ch<'0'||ch>'9') t|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1){ read(x),read(x1...); }
template<class T>
inline void write(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
template<>
inline void write(bool x){ putchar(x?'1':'0'); }
template<>
inline void write(char c){ putchar(c); }
template<>
inline void write(char *s){ while(*s!='\0') putchar(*s++); }
template<>
inline void write(const char *s){ while(*s!='\0') putchar(*s++); }
template<class T,class ...T1>
inline void write(T x,T1 ...x1){ write(x),write(x1...); }
template<class T>
inline bool checkMax(T &x,T y){ return x<y?x=y,1:0; }
template<class T>
inline bool checkMin(T &x,T y){ return x>y?x=y,1:0; }
const int MAXN=1e5+10;
int N,Q,a[MAXN];
#define ls (p<<1)
#define rs (p<<1|1)
struct St
{
	int l,r,cov,len,cnt,lx[2],rx[2],val[2];
	bool rev;
}Tr[MAXN<<2];
inline void pushUp(int p)
{
	for(int i=0;i<=1;++i)
	{
		Tr[p].lx[i]=Tr[ls].lx[i],Tr[p].rx[i]=Tr[rs].rx[i];
		if(Tr[ls].cnt==(i==1?Tr[ls].len:0)) checkMax(Tr[p].lx[i],Tr[ls].len+Tr[rs].lx[i]);
		if(Tr[rs].cnt==(i==1?Tr[rs].len:0)) checkMax(Tr[p].rx[i],Tr[rs].len+Tr[ls].rx[i]);
		Tr[p].val[i]=std::max(std::max(Tr[ls].val[i],Tr[rs].val[i]),Tr[ls].rx[i]+Tr[rs].lx[i]);
	}
	Tr[p].cnt=Tr[ls].cnt+Tr[rs].cnt;
}
inline void pushDown(int p)
{
	if(~Tr[p].cov)
	{
		Tr[ls].cnt=Tr[p].cov*Tr[ls].len,Tr[rs].cnt=Tr[p].cov*Tr[rs].len;
		int v=Tr[p].cov;
		Tr[ls].lx[v]=Tr[ls].rx[v]=Tr[ls].val[v]=Tr[ls].len;
		Tr[rs].lx[v]=Tr[rs].rx[v]=Tr[rs].val[v]=Tr[rs].len;
		Tr[ls].lx[v^1]=Tr[ls].rx[v^1]=Tr[ls].val[v^1]=0;
		Tr[rs].lx[v^1]=Tr[rs].rx[v^1]=Tr[rs].val[v^1]=0;
		Tr[ls].cov=Tr[rs].cov=Tr[p].cov;
		Tr[p].rev=0;Tr[p].cov=-1;
	}
	if(Tr[p].rev)
	{
		Tr[ls].cnt=Tr[ls].len-Tr[ls].cnt,Tr[rs].cnt=Tr[rs].len-Tr[rs].cnt;
		if(~Tr[ls].cov) Tr[ls].cov^=1;
		else Tr[ls].rev^=1;
		if(~Tr[rs].cov) Tr[rs].cov^=1;
		else Tr[rs].rev^=1;
		std::swap(Tr[ls].lx[0],Tr[ls].lx[1]),std::swap(Tr[ls].rx[0],Tr[ls].rx[1]);
		std::swap(Tr[rs].lx[0],Tr[rs].lx[1]),std::swap(Tr[rs].rx[0],Tr[rs].rx[1]);
		std::swap(Tr[ls].val[0],Tr[ls].val[1]),std::swap(Tr[rs].val[0],Tr[rs].val[1]);
		Tr[p].rev=0;
	}
}
inline void Cover(int p,int c)
{
	Tr[p].cov=c,Tr[p].rev=0;
	Tr[p].cnt=c*Tr[p].len;
	Tr[p].lx[c]=Tr[p].rx[c]=Tr[p].val[c]=Tr[p].len;
	Tr[p].lx[c^1]=Tr[p].rx[c^1]=Tr[p].val[c^1]=0;
}
inline void Reverse(int p)
{
	Tr[p].cnt=Tr[p].len-Tr[p].cnt;
	Tr[p].rev^=1;
	std::swap(Tr[p].lx[0],Tr[p].lx[1]),std::swap(Tr[p].rx[0],Tr[p].rx[1]);
	std::swap(Tr[p].val[0],Tr[p].val[1]);
}
void build(int p,int l,int r)
{
	Tr[p].l=l,Tr[p].r=r,Tr[p].cov=-1,Tr[p].rev=0;
	Tr[p].len=r-l+1;
	if(l==r)
	{
		int v=a[l];
		Tr[p].cnt=v;
		Tr[p].lx[v]=Tr[p].rx[v]=Tr[p].val[v]=1;
		Tr[p].lx[v^1]=Tr[p].rx[v^1]=Tr[p].val[v^1]=0;
		return ;
	}
	int mid=(l+r)>>1;
	build(ls,l,mid),build(rs,mid+1,r);
	pushUp(p);
}
void modifyCov(int p,int l,int r,int c)
{
	pushDown(p);
	if(l<=Tr[p].l&&Tr[p].r<=r) return Cover(p,c);
	int mid=(Tr[p].l+Tr[p].r)>>1;
	if(l<=mid) modifyCov(ls,l,r,c);
	if(mid<r) modifyCov(rs,l,r,c);
	pushUp(p);
}
void modifyRev(int p,int l,int r)
{
	pushDown(p);
	if(l<=Tr[p].l&&Tr[p].r<=r) return Reverse(p);
	int mid=(Tr[p].l+Tr[p].r)>>1;
	if(l<=mid) modifyRev(ls,l,r);
	if(mid<r) modifyRev(rs,l,r);
	pushUp(p);
}
int queryCnt(int p,int l,int r)
{
	pushDown(p);
	if(l<=Tr[p].l&&Tr[p].r<=r) return Tr[p].cnt;
	int res=0,mid=(Tr[p].l+Tr[p].r)>>1;
	if(l<=mid) res+=queryCnt(ls,l,r);
	if(mid<r) res+=queryCnt(rs,l,r);
	return res;
}
St queryVal(int p,int l,int r)
{
	pushDown(p);
	if(l<=Tr[p].l&&Tr[p].r<=r) return Tr[p];
	int mid=(Tr[p].l+Tr[p].r)>>1;
	if(mid<l) return queryVal(rs,l,r);
	else if(r<=mid) return queryVal(ls,l,r);
	else
	{
		St res,L=queryVal(ls,l,r),R=queryVal(rs,l,r);
		res.cnt=L.cnt+R.cnt;
		for(int i=0;i<=1;++i)
		{
			res.lx[i]=L.lx[i];
			if(i==0&&L.cnt==0) res.lx[i]+=R.lx[i];
			if(i==1&&L.cnt==L.len) res.lx[i]+=R.lx[i];
			res.rx[i]=R.rx[i];
			if(i==0&&R.cnt==0) res.rx[i]+=L.rx[i];
			if(i==1&&R.cnt==R.len) res.rx[i]+=L.rx[i];
			res.val[i]=std::max(std::max(L.val[i],R.val[i]),L.rx[i]+R.lx[i]);
		}
		return res;
	}
}
int main()
{
	// freopen(".in","r",stdin);
	// freopen(".out","w",stdout);
	read(N,Q);
	for(int i=1;i<=N;++i) read(a[i]);
	build(1,1,N);
	for(int opt,ql,qr;Q--;)
	{
		read(opt,ql,qr);++ql,++qr;
		if(opt<=1) modifyCov(1,ql,qr,opt);
		else if(opt==2) modifyRev(1,ql,qr);
		else if(opt==3) write(queryCnt(1,ql,qr),'\n');
		else if(opt==4) write(queryVal(1,ql,qr).val[1],'\n');
	}
	return 0;
}
/*

*/
相关文章