写在前面
傻逼线段树题,码量第一次超 \(6.5k\)
因为不能考 \(NOIp\) 一气之下把它肝了(放屁,你是因为想看小说,而做数据结构不用脑子,好在DJ来的时候方便掩饰
个人感觉理解本题后会对线段树有更为深刻的理解,亦可增加对线段树的套路用法,了解各操作之间的优先级
本题解陈述尽量详细周全,若有赘述的地方请自行跳过,如果有什么疑问也可在评论区提出
简述题意
给定一段 \(01\) 序列,有 \(5\) 种操作
0、一段区间变成 \(0\)
1、一段区间变成 \(1\)
2、对一段区间取反
3、询问一段区间内有多少个 \(1\)
4、询问一段区间内最多有多少个连续的 \(1\)
序列长为 \(n\) ,有 \(m\) 个操作(数据范围:\(1 \le n,m\le 10^5\))
Solution
操作 \(0,1,3\) 都比较好解决,线段树基本操作,这里不赘述
主要是 \(2,4\) 操作
对于 \(4\) 操作,我们不难想到可以用 \(max\) 维护区间最长的 \(1\) ,分别用 \(lmax\) 和 \(rmax\) 来维护左端点最长的 &1& 和右端点最长的 \(1\)
在上传是注意 \(max\) 要和左右儿子的 \(max\) ,以及左儿子的 \(rmax\) 加右儿子的 \(lmax\) 这三个值中取最大值
(相信做过 GSS3 都能直接想到 \(4\) 的处理方法,没做过也没有关系,思路应该也是比较好理解的)
那加上 \(2\) 操作怎么融合,另设一个懒标记 \(rev\) 来表示是否翻转
1、因为有两种修改操作,考虑懒标记优先级:因为 \(0, 1\) 的操作会把取反操作覆盖掉,所以覆盖的优先级要高于反转的优先级
2、只有一个 \(max,lmax,rmax\),每次翻转后怎么更新:直接设两个不就好了,把 \(0, 1\) 的 \(max, lmax, rmax\) 都存下来,翻转的时候只要交换就好了
3、翻转后如何求和:这个比较简单,用长度减掉原来的 \(sum\) 就好了
在询问 \(4\) 操作时,要注意两端序列的合并应使用结构体回传(好像较为复杂的线段树题都需要这样处理)
ACcode
由于码量较大,请注意保护眼睛
尽可能的做到了排版整齐,变量名称清新易懂,过程简洁明了,还附有一定的注释来帮助理解
可以考虑用循环减少码量,但我感觉拆开写更方便理解(善用位运算可以省不少力)
/*
Work by: Suzt_ilymics
Knowledge: 傻逼线段树
Time: O(??)
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define lson i << 1
#define rson i << 1 | 1
#define orz cout<<"lkp ak ioi"<<endl;
using namespace std;
const int MAXN = 1e5+5;
const int INF = 1;
const int mod = 1;
struct Tree{
int len, lazy, sum, lmax[2], rmax[2], max[2], rev;
}tree[MAXN << 2];
int n, m;
int a[MAXN];
int read(){
int s = 0, w = 1;
char ch = getchar();
while(ch < '0' || ch > '9') { if(ch == '-') w = -1; ch = getchar(); }
while(ch >= '0' && ch <= '9') s = (s << 1) + (s << 3) + ch - '0' , ch = getchar();
return s * w;
}
int max(int x, int y){ return x > y ? x : y; }
void push_up(int i){//上传
tree[i].sum = tree[lson].sum + tree[rson].sum;//维护区间和
if(tree[lson].sum == tree[lson].len) tree[i].lmax[1] = tree[lson].lmax[1] + tree[rson].lmax[1];//维护
else tree[i].lmax[1] = tree[lson].lmax[1];
if(tree[rson].sum == tree[rson].len) tree[i].rmax[1] = tree[rson].rmax[1] + tree[lson].rmax[1];
else tree[i].rmax[1] = tree[rson].rmax[1];
tree[i].max[1] = max(tree[lson].max[1], tree[rson].max[1]);//维护区间最多有的连续的1,取左区间最大值、右区间最大值、左区间右边最大值和右区间左边最大值的和三个中的最大值
tree[i].max[1] = max(tree[i].max[1], tree[lson].rmax[1] + tree[rson].lmax[1]);
if(tree[lson].sum == 0) tree[i].lmax[0] = tree[lson].lmax[0] + tree[rson].lmax[0];//维护
else tree[i].lmax[0] = tree[lson].lmax[0];
if(tree[rson].sum == 0) tree[i].rmax[0] = tree[rson].rmax[0] + tree[lson].rmax[0];
else tree[i].rmax[0] = tree[rson].rmax[0];
tree[i].max[0] = max(tree[lson].max[0], tree[rson].max[0]);//维护区间最多有的连续的0,取左区间最大值、右区间最大值、左区间右边最大值和右区间左边最大值的和三个中的最大值
tree[i].max[0] = max(tree[i].max[0], tree[lson].rmax[0] + tree[rson].lmax[0]);
return ;
}
void build(int i, int l, int r){
tree[i].len = r - l + 1, tree[i].lazy = -1, tree[i].rev = 0;
if(l == r) {
tree[i].sum = a[l];
tree[i].max[0] = tree[i].lmax[0] = tree[i].rmax[0] = (a[l] == 0);
tree[i].max[1] = tree[i].lmax[1] = tree[i].rmax[1] = (a[l] == 1);
return ;
}
int mid = (l + r) >> 1;
build(lson, l, mid), build(rson, mid + 1, r);
push_up(i);
return ;
}
void push_down(int i){//下穿,注意优先级
if(tree[i].lazy != -1){
tree[i].rev = 0;
int val = tree[i].lazy;
tree[lson].sum = tree[lson].len * val;
tree[rson].sum = tree[rson].len * val;
tree[lson].lazy = tree[rson].lazy = val;
tree[lson].rev = tree[rson].rev = 0;
tree[lson].lmax[val ^ 1] = tree[lson].rmax[val ^ 1] = tree[lson].max[val ^ 1] = 0;
tree[rson].lmax[val ^ 1] = tree[rson].rmax[val ^ 1] = tree[rson].max[val ^ 1] = 0;
tree[lson].lmax[val] = tree[lson].rmax[val] = tree[lson].max[val] = tree[lson].len;
tree[rson].lmax[val] = tree[rson].rmax[val] = tree[rson].max[val] = tree[rson].len;
tree[i].lazy = -1;
}
if(tree[i].rev){
tree[lson].sum = tree[lson].len - tree[lson].sum;
tree[rson].sum = tree[rson].len - tree[rson].sum;
if(tree[lson].lazy != -1) tree[lson].lazy ^= 1;
else tree[lson].rev ^= 1;
if(tree[rson].lazy != -1) tree[rson].lazy ^= 1;
else tree[rson].rev ^= 1;
swap(tree[lson].max[0], tree[lson].max[1]);
swap(tree[lson].lmax[0], tree[lson].lmax[1]);
swap(tree[lson].rmax[0], tree[lson].rmax[1]);
swap(tree[rson].max[0], tree[rson].max[1]);
swap(tree[rson].lmax[0], tree[rson].lmax[1]);
swap(tree[rson].rmax[0], tree[rson].rmax[1]);
tree[i].rev = 0;
}
return ;
}
void change01(int i, int l, int r, int L, int R, int k){//01覆盖操作
push_down(i);
if(L <= l && r <= R){
tree[i].sum = tree[i].len * k;
tree[i].lazy = k;
tree[i].lmax[k] = tree[i].rmax[k] = tree[i].max[k] = tree[i].len;
tree[i].lmax[k ^ 1] = tree[i].rmax[k ^ 1] = tree[i].max[k ^ 1] = 0;
return ;
}
int mid = (l + r) >> 1;
if(mid < L) change01(rson, mid + 1, r, L, R, k);
else if(mid >= R) change01(lson, l, mid, L, R, k);
else change01(lson, l, mid, L, mid, k), change01(rson, mid + 1, r, mid + 1, R, k);
push_up(i);
}
void changef(int i, int l, int r, int L, int R){//取反操作
push_down(i);
if(L <= l && r <= R){
tree[i].sum = tree[i].len - tree[i].sum;
tree[i].rev ^= 1;
swap(tree[i].max[1], tree[i].max[0]);
swap(tree[i].lmax[1], tree[i].lmax[0]);
swap(tree[i].rmax[1], tree[i].rmax[0]);
return ;
}
int mid = (l + r) >> 1;
if(mid < L) changef(rson, mid + 1, r, L, R);
else if(mid >= R) changef(lson, l, mid, L, R);
else changef(lson, l, mid, L, mid), changef(rson, mid + 1, r, mid + 1, R);
push_up(i);
}
int get_sum(int i, int l, int r, int L, int R){//区间和
push_down(i);
if(L <= l && r <= R){
return tree[i].sum;
}
int mid = (l + r) >> 1, ans = 0;
if(mid < L) return get_sum(rson, mid + 1, r, L, R);
else if(mid >= R) return get_sum(lson, l, mid, L, R);
else return get_sum(lson, l, mid, L, mid) + get_sum(rson, mid + 1, r, mid + 1, R);
}
Tree get_max(int i, int l, int r, int L, int R){//区间最大值
// cout<<i<<" "<<l<<" "<<r<<" "<<L<<" "<<R<<endl;
push_down(i);
if(L <= l && r <= R){ return tree[i]; }
int mid = (l + r)>> 1;
if(mid < L) return get_max(rson, mid + 1, r, L, R);
else if(mid >= R) return get_max(lson, l, mid, L, R);
else {
Tree ans, ansl = get_max(lson, l, mid, L, mid), ansr = get_max(rson, mid + 1, r, mid + 1, R);
ans.sum = ansl.sum + ansr.sum;
ans.lmax[1] = ansl.lmax[1], ans.lmax[0] = ansl.lmax[0];
if(ansl.sum == ansl.len) ans.lmax[1] += ansr.lmax[1];
if(ansl.sum == 0) ans.lmax[0] += ansr.lmax[0];
ans.rmax[1] = ansr.rmax[1], ans.rmax[0] = ansr.rmax[0];
if(ansr.sum == ansr.len) ans.rmax[1] += ansl.rmax[1];
if(ansr.sum == 0) ans.rmax[0] += ansl.rmax[0];
ans.max[1] = max(ansl.max[1], ansr.max[1]);
ans.max[1] = max(ans.max[1], ansl.rmax[1] + ansr.lmax[1]);
ans.max[0] = max(ansl.max[0], ansr.max[0]);
ans.max[0] = max(ans.max[0], ansl.rmax[0] + ansr.lmax[0]);
return ans;
}
}
int main()
{
n = read(), m = read();
for(int i = 1; i <= n; ++i) a[i] = read();
build(1, 1, n);
for(int i = 1, opt, l, r; i <= m; ++i){
opt = read(), l = read() + 1, r = read() + 1;
if(opt == 0){ change01(1, 1, n, l, r, 0); }
if(opt == 1){ change01(1, 1, n, l, r, 1); }
if(opt == 2){ changef(1, 1, n, l, r); }
if(opt == 3){ printf("%d\n", get_sum(1, 1, n, l, r)); }
if(opt == 4){ printf("%d\n", get_max(1, 1, n, l, r).max[1]); }
}
return 0;
}