P6492 [COCI2010-2011#6] STEP(线段树维护左右区间pushup)

题目大意：

\(~~\)初始给定一个长度为n的字符序列a,初始序列中全是\(~\)L
\(~~\)共有q次修改，修改a\(_{x}\)为：L\(\rightarrow\)\(~~\)or\(~~\)R\(\rightarrow\)L
\(~~\)求一个区间[L,R]内不存在连续的L,R的最大长度，即L和R交替出现的最大长度

题目思路：

\(~~\)经典用线段树维护区间lmax,rmax,maxn,len来求区间内某种性质的字串最大长度
\(~~\)同时因为我们的字串要求L,R交替出现，所以我们还需要记住区间最左，最右的字母
\(~~\)区间转移：
\(~~~~\)lmax[u] = lmax[ls],rmax[u] = rmax[rs]
\(~~~~\)如果pr[ls]\(~\)!=\(~\)pl[rs]说明左右子区间字母不同，可以接在一起，所以：
\(~~~~\)maxn[u]\(~\)=\(~\)max(maxn,rmax[ls]+lmax[rs])
\(~~~~\)特别注意此时左右区间可以拼接的时候如果lmax[ls]\(~\)==\(~\)len[ls]那么lmax[u]\(~\)=len[ls]+lmax[rs]

同理如果rmax[rs]\(~\)==\(~\)len[rs]那么rmax[u]\(~\)=len[rs]+rmax[ls]

代码实现：

# include<bits/stdc++.h>
using namespace std;
# define int long long
# define ls u<<1
# define rs u<<1|1
const int N = 2e5 + 10;
int a[N], p, n, m;
struct segtree {
	int lmax[4 * N], rmax[4 * N], maxn[N << 2];
	int pl[N << 2], pr[N << 2], len[N << 2];
	void pushup(int u) {
		lmax[u] = lmax[ls];
		rmax[u] = rmax[rs];
		pl[u] = pl[ls];
		pr[u] = pr[rs];
		maxn[u] = max(maxn[ls], maxn[rs]);
		if (pr[ls] != pl[rs]) {
			maxn[u] = max(maxn[u], rmax[ls] + lmax[rs]);
			if (maxn[ls] == len[ls]) {
				lmax[u] = len[ls] + lmax[rs];
			}
			if (maxn[rs] == len[rs]) {
				rmax[u] = rmax[ls] + len[rs];
			}
		}
	}


	void build(int u, int l, int r) {
		len[u] = r - l + 1;
		if (l == r) {
			lmax[u] = rmax[u] = maxn[u] = 1;
			pl[u] = pr[u] = 1;
			len[u] = 1;
			return;
		}
		int mid = l + r >> 1;
		build(ls, l, mid);
		build(rs, mid + 1, r);
		pushup(u);
	}

	void modify(int u, int l, int r, int L, int R, int c) {
		if (L <= l && r <= R) {
			pl[u] ^= 1;
			pr[u] ^= 1;
			return;
		}
		int mid = l + r >> 1;
		if (L <= mid) modify(ls, l, mid, L, R, c);
		if (mid + 1 <= R) modify(rs, mid + 1, r, L, R, c);
		pushup(u);
	}

	int query(int u, int l, int r, int L, int R) {
		if (l >= L && r <= R) {
		}
		int mid = l + r >> 1;
		if (R <= mid) return query(ls, l, mid, L, R);
		else if (L > mid) return query(rs, mid + 1, r, L, R);
		else return max(query(ls, l, mid, L, mid), query(rs, mid + 1, r, mid + 1, R));

	}
} tr;

signed main() {
	cin >> n >> m;
	tr.build(1, 1, n);

	while (m--) {
		int x;
		cin >> x;
		tr.modify(1, 1, n, x, x, 1);
		cout << max(tr.maxn[1], max(tr.lmax[1], tr.rmax[1])) << endl;
	}


	return 0;
}