17.CF739C Alyona and towers 区间合并线段树
给定序列,要求支持区间加,以及查询最长先增后减子区间(单峰序列)长度
非常典型的区间合并线段树,记录左右起LIS,LCS,单峰
洛谷传送门:CF739C Alyona and towers - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
CF传送门:Problem - 739C - Codeforces
题目分析
CSDN的SVG图像显示可能有点问题?
给定序列,要求支持区间加,以及查询最长先增后减子区间(单峰序列)长度。
区间和并线段树,我们需要记录每个区间的最大的左端点起长度(
)、左端点起
长度(
)、右端点结束
长度(
)、右端点结束
长度(
)、左端点起单峰长度
、右端点起单峰长度
,无限制单峰长度
,以及左右端点
。
考虑合并的方式:对于两个区间,在合并的方式,容易想到端点的关系决定了合并后的结果:
我们首先需要对合并的结果进行初始化,我们设合并后的信息为,加号右侧信息(就是右区间)
,则:
res.lv = lv, res.rv = x.rv;
res.llis = llis, res.llds = llds;
res.rlis = x.rlis, res.rlds = x.rlds;
res.plm = plm, res.prm = x.prm;
res.ans = max(ans, x.ans);
res.len = len + x.len;
- 左区间右端点值
右区间左端点值:
因为端点大小关系,此时一定无法合并。
- 对于左端点起的
合并:分两种情况:
- 左区间左端点起
长度等于左区间长度,即 左区间整个区间都是
序列:
+
+此时只需要直接把右区间左起长度+左区间长度合并即可:
if(llis == len) res.llis += x.llis;
- 否则不能合并,因为两个左起序列之间不严格递增:
+
+
- 对于右端点结束的
合并,同样分两种情况:
- 有区间右端点结束
长度等于右区间长度,即 右区间整个区间都是
序列:
+
+此时只需要直接把右区间长度+左区间右端点结束长度:
if(x.rlis == x.len) res.rlis += rlis;
- 否则不能合并:
+
+
- 对于峰值位于右区间的单峰:
- 如果右区间单峰长度等右区间长度:
+
+那么就可以与左区间右端点结束合并:
if(x.prm == x.len) res.prm += rlis;
- 如果左区间
长度等于左区间长度:
+
+ Viewer does not support full SVG 1.1
if(llis == len) res.plm = max(res.plm, len + x.plm);
- 然后需要加入合并过程中损失的信息:左区间右端点结束
和右区间左端点起单峰:
+
+ Viewer does not support full SVG 1.1
res.ans = max(res.ans, rlis + x.plm);
- 类似的,当左区间右端点值
右区间左端点值时,我们对
和单峰、答案采取类似的方式进行合并即可。
综上所述,我们可以得到区间合并信息的过程:
struct info{
int lv = 0, rv = 0;
int ans = 1, llis = 1, llds = 1, rlis = 1, rlds = 1, plm = 1, prm = 1, len = 1;
info() {}
info(int val): lv(val), rv(val) {}
info operator+ (info &x) {
info res;
res.lv = lv, res.rv = x.rv, res.ans = max(ans, x.ans);
res.llis = llis, res.llds = llds;
res.rlis = x.rlis, res.rlds = x.rlds;
res.plm = plm, res.prm = x.prm;
res.len = len + x.len;
if(rv < x.lv){
if(llis == len) res.llis += x.llis;
if(x.rlis == x.len) res.rlis += rlis;
if(x.prm == x.len) res.prm += rlis;
if(llis == len) res.plm = max(res.plm, len + x.plm);
res.ans = max(res.ans, rlis + x.plm);
}
else if(rv > x.lv){
if(llds == len) res.llds += x.llds;
if(x.rlds == x.len) res.rlds += rlds;
if(plm == len) res.plm += x.llds;
if(x.rlds == x.len) res.prm = max(res.prm, x.len + prm);
res.ans = max(res.ans, prm + x.llds);
}
return res;
}
}tree[N << 2];
剩下的就是线段树板子了。
Code
#include <bits/stdc++.h>
#pragma gcc optimize("O2")
#pragma g++ optimize("O2")
#define int long long
#define endl '\n'
using namespace std;
const int N = 4e5 + 10, MOD = 1e9 + 7;
int a[N];
namespace ffastIO {
const int bufl = 1 << 15;
char buf[bufl], *s = buf, *t = buf;
inline int fetch() {
if (s == t) { t = (s = buf) + fread(buf, 1, bufl, stdin); if (s == t) return EOF; }
return *s++;
}
inline int read() {
int a = 0, b = 1, c = fetch();
while (!isdigit(c))b ^= c == '-', c = fetch();
while (isdigit(c)) a = a * 10 + c - 48, c = fetch();
return b ? a : -a;
}
}
using ffastIO::read;
namespace SegTree{
#define ls rt << 1
#define rs rt << 1 | 1
#define lson ls, l,
#define rson rs, mid + 1,
struct info{
int lv = 0, rv = 0;
int ans = 1, llis = 1, llds = 1, rlis = 1, rlds = 1, plm = 1, prm = 1, len = 1;
info() {}
info(int val): lv(val), rv(val) {}
info operator+ (info &x) {
info res;
res.lv = lv, res.rv = x.rv, res.ans = max(ans, x.ans);
res.llis = llis, res.llds = llds;
res.rlis = x.rlis, res.rlds = x.rlds;
res.plm = plm, res.prm = x.prm;
res.len = len + x.len;
if(rv < x.lv){
if(llis == len) res.llis += x.llis;
if(x.rlis == x.len) res.rlis += rlis;
if(x.prm == x.len) res.prm += rlis;
if(llis == len) res.plm = max(res.plm, len + x.plm);
res.ans = max(res.ans, rlis + x.plm);
}
else if(rv > x.lv){
if(llds == len) res.llds += x.llds;
if(x.rlds == x.len) res.rlds += rlds;
if(plm == len) res.plm += x.llds;
if(x.rlds == x.len) res.prm = max(res.prm, x.len + prm);
res.ans = max(res.ans, prm + x.llds);
}
return res;
}
}tree[N << 2];
int lazy[N << 2];
inline void push_up(int rt){ tree[rt] = tree[ls] + tree[rs]; }
inline void push_down(int rt){
if(!lazy[rt]) return;
tree[ls].lv += lazy[rt], tree[ls].rv += lazy[rt];
tree[rs].lv += lazy[rt], tree[rs].rv += lazy[rt];
lazy[ls] += lazy[rt], lazy[rs] += lazy[rt];
lazy[rt] = 0;
}
void build(int rt, int l, int r){
lazy[rt] = 0;
if(l == r) return (void)(tree[rt] = info(a[l]));
int mid = l + r >> 1;
build(lson), build(rson);
push_up(rt);
}
void update(int rt, int l, int r, int L, int R, int val){
if(l >= L && r <= R){
tree[rt].lv += val, tree[rt].rv += val;
lazy[rt] += val;
return;
}
push_down(rt);
int mid = l + r >> 1;
if(mid >= L) update(lson, L, R, val);
if(mid < R) update(rson, L, R, val);
push_up(rt);
}
}
#define SEGRG 1, 1,
inline void solve(){
int n = read();
for(int i = 1; i <= n; i++) a[i] = read();
SegTree::build(SEGRG);
int m = read();
for(int i = 1; i <= m; i++){
int l = read(), r = read(), d = read();
SegTree::update(SEGRG, l, r, d);
cout << SegTree::tree[1].ans << endl;
}
}
signed main(){
solve();
return 0;
}