P2572 [SCOI2010]序列操作

写在前面

傻逼线段树题,码量第一次超 \(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;
}
上一篇:帆帆的 KD-Tree 全家桶


下一篇:043-PHP简单获得一个类对应的反射信息