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;
}
同类题型:
- E. Non-Decreasing Dilemma
\(~~~~\)代码:
最新文章
- 体验Visual Studio 2015 之 MVC - 视图组建
- 15-前端开发之JavaScript
- wf(六)
- Android菜鸟成长记13 -- 初识application
- iOS UITableViewCell的分割线向左延长15(cell长度为全宽)
- 卸载Photoshop
- ionic cordova
- virtual box ubuntu卡在开机光标
- Oracle 存储过程包
- poj 3150 Cellular Automaton
- 两个由于php.ini配置错误导致的报错:ajax图片上传报错和exec报错
- 李洪强漫谈iOS开发[C语言-025]-赋值运算符案例
- Android工程师必会做的20道题
- [BZOJ 3942] [Usaco2015 Feb] Censoring 【KMP】
- pythonj基础之 多线程
- XFdtd 7.3.2发布增强生物电磁学中的核磁共振功能
- laravel 控制器类DB类操作
- Ubunut操作系统下nDPI的部署及简单使用
- char *s="string"和char s[]="string"的区别
- &#39;pip&#39; 不是内部或外部命令