P6492 STEP(线段树维护左右区间pushup)

题目链接

题目描述：

给定一个长度为\(~\)n\(~\)的字符序列\(~\)a，初始时序列中全部都是字符\(~\)L。

有\(~\)q\(~\)次修改，每次给定一个\(~\)x，做出如下变化：

\(~~\) 1. a\(_{x}\)\(~\)=\(~\)L \(\rightarrow\)a\(_{x}\)\(~\)=\(~\)R

\(~~\) 2. a\(_{x}\)\(~\)=\(~\)R \(\rightarrow\)a\(_{x}\)\(~\)=\(~\)L

对于一个只含字符 L，R 的字符串 s，若其中不存在连续的 L 和 R，则称 s 满足要求。

每次修改后，请输出当前序列 a 中最长的满足要求的连续子串的长度。

题目思路

\(~~\) 利用线段树来维护左右区间进而维护区间某一属性的最大值

\(~~\)维护区间的lmax,rmax，即以左端点开始的最大值和以右端点开始的最大值

\(~~\)这样一个区间的最大值就可以通过子区间的maxn,lmax,rmax来维护

具体措施如下：

\(~~\) 1. 当两个子区间相接的地方不能连在一起时：

\(~~~~~\) 那父区间的最大值只能由左右区间的最大值转移而来： maxn[u]\(~\)=\(~\) max(maxn[ls],maxn[rs]);

\(~~~~~\) 而父区间的lmax由左区间的lmax转移来，rmax由右区间的rmax转移来： lmax[u]\(~\)=\(~\)lmax[ls],rmax[u]\(~\)=\(~\)rmax[rs];

\(~~\) 2. 当两个子区间相接的地方能连在一起时：

\(~~~~~\) 父区间的最大值就要考虑存不存在左区间的\(~\)“rmax”\(~\)和右区间的\(~\)“lmax”\(~\)连在一起比左右区间的maxn大的情况了：

\(~~~~~~\)maxn[u]\(~\)=\(~\)max(rmax[ls]+lmax[rs],max(maxn[ls],maxn[rs]));

\(~~~~~\) 同时因为左右区间可以连接在一块，所以在转移rmax和lmax也要考虑到是否会存在连接在一起的可能：

\(~~~~~~\) if(rmax[rs]\(~\)=\(~\)整个右区间的长度):

\(~~~~~~~~~~\) rmax[u]\(~\)=\(~\)rmax[ls]\(~\)+\(~\)右区间长度;

\(~~~~~~\) if(lmax[ls]\(~\)=\(~\)整个左区间的长度):

\(~~~~~~~~~~\) lmax[u]\(~\)=\(~\)lmax[rs]\(~\)+\(~\)左区间长度;

综上所述我们就完成了线段树的维护了，根据我们的思路，这道题在维护的时候还需要同时记录每个区间的区间长度，左右边界的元素：

即len[\(~\)],pl[\(~\)],pr[\(~\)]

代码实现

# 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;

}