题目大意

维护一个 \(01\) 序列最长的连续相邻两个数不同的子序列的长度

解析

很裸的线段树题。。。

要维护的信息很多

区间长度
区间最左端点
区间最右端点
区间最长前缀
区间最长后缀
区间最终的答案

前三个直接从左右儿子获取即可

区间最长前缀先为左儿子的区间最长前缀

如果左儿子的区间最长前缀为左区间的长度，那么考虑它能不能和右儿子拼接，更新答案

右区间最长前缀同理

最终答案是 左儿子的最终答案，右儿子的最终答案，左儿子和右儿子能否拼接的答案，本区间的最长前缀，本区间的最长后缀 中的最大值

于是你明白了为什么要维护辣么多东西

\(Code\)

#include<cstdio>

#include<iostream>

#define ls (k << 1)

#define rs (ls | 1)

using namespace std;

const int N = 2e5 + 5;

int n , q;

struct segment{

	int len , l , r , p , s , v;

}seg[N << 2];

inline void pushup(int k)

{

	seg[k].l = seg[ls].l , seg[k].r = seg[rs].r;

	seg[k].len = seg[ls].len + seg[rs].len;

	seg[k].p = seg[ls].p;

	if (seg[ls].p == seg[ls].len && seg[ls].r ^ seg[rs].l) seg[k].p = seg[ls].p + seg[rs].p;

	seg[k].s = seg[rs].s;

	if (seg[rs].s == seg[rs].len && seg[ls].r ^ seg[rs].l) seg[k].s = seg[rs].s + seg[ls].s;

	seg[k].v = (max(seg[k].p , seg[k].s) , max(seg[ls].v , seg[rs].v));

	if (seg[ls].r ^ seg[rs].l) seg[k].v = max(seg[k].v , seg[ls].s + seg[rs].p);

}

inline void build(int l , int r , int k)

{

	if (l == r)

	{

		seg[k].l = seg[k].r = 0;

		seg[k].len = seg[k].p = seg[k].s = seg[k].v = 1;

		return;

	}

	int mid = (l + r) >> 1;

	build(l , mid , ls) , build(mid + 1 , r , rs);

	pushup(k);

}

inline void update(int x , int l , int r , int k)

{

	if (l == r && l == x)

	{

		seg[k].l = seg[k].r = seg[k].l ^ 1;

		return;

	}

	int mid = (l + r) >> 1;

	if (x <= mid) update(x , l , mid , ls);

	else update(x , mid + 1 , r , rs);

	pushup(k);

}

int main()

{

	scanf("%d%d" , &n , &q);

	build(1 , n , 1);

	int x;

	for(; q; q--)

	{

		scanf("%d" , &x);

		update(x , 1 , n , 1);

		printf("%d\n" , seg[1].v);

	}

}

巴特西

[COCI2010-2011#6] STEP

题目大意

解析

\(Code\)

最新文章

热门文章