单峰数列
- 题意对于一个整数数列，如果其先严格递增，然后在某一点后严格递减，我们称这个数列为单峰数列（严格递增和严格递减的部分均要是非空）。
给定长度为 n 的整数数列 \(a_1,a_2,…,a_n\)，请你支持 q 次操作：
1 l r x：将 \(a_l,a_{l+1},…,a_r\) 的每个数加 x。2 l r：判断 \(a_l,a_{l+1},…,a_r\) 的元素是否全都相同。3 l r：判断 \(a_l,a_{l+1},…,a_r\) 是否严格升序排序。当 \(l=r\) 时，认为符合严格升序排序。4 l r：判断 \(a_l,a_{l+1},…,a_r\) 是否严格降序排序。当 \(l=r\) 时，认为符合严格降序排序。5 l r：判断 \(a_l,a_{l+1},…,a_r\) 是否为单峰数列。保证 \(r−l+1≥3\)。
- \(n (3≤n≤10^5), a1,a2,…,an (0≤ai≤10^9), q (1≤q≤2×10^5), −10^9≤x≤10^9\)
赛时前面开的比较慢，这题就稍微有点急，没鼠标和习惯问题（还是练习太少了，每次写完线段树的题目都没仔细想），导致赛时没debug出来，但是思路一眼时对的：
对于这种区间信息合并和整个区间有关的，不是某个值的信息维护，一般考虑每个区间的 \(pre, suf\), 和一些关键性质，区间加法应该学过线段树的都会，这里不详细讲了。这题的关键性质就是每个区间其他信息的关系，记相同为same，上升为add， 下降是sub，单峰为mou，合并时这样维护（记父亲区间为c,左右儿子是a, b：
对于 same, 父亲如果要是 same，则左右一定也是 same 且相接的地方是相等的，即 c.same = a.same && b.same && a.suf == b.pre
对于 add，父亲如果要是 add，则左右一定也是 add 且相接的地方是递增的，即 c.add = a.add && b.add && a.suf < b.pre
对于 sub，父亲如果要是 sub，则左右一定也是 sub 且相接的地方是递减的，即 c.sub = a.sub && b.sub && a.suf > b.pre
特别的对于 mou，我们定义小于3的区间 mou = 0, 这里单峰有三种情况
1.左增右减，相接的地方无论在哪都会是单峰
2.左边单峰，右边一定是递减的，否则会有一个新的峰
3.右边单峰, 左边一定是上升的，否则会有一个新的峰
剩下的合并就是左右的 pre 和 suf 了，c.pre = a.pre, c.suf = b.suf
Info merge(const Info& a, const Info& b) {
Info c;
if(a.same && b.same && a.suf == b.pre) c.same = 1;
else c.same = 0;
if(a.add && b.add && a.suf < b.pre) c.add = 1;
else c.add = 0;
if(a.sub && b.sub && a.suf > b.pre) c.sub = 1;
else c.sub = 0;
c.len = a.len + b.len;
if(c.len >= 3) {
if((a.add && b.sub) ||
(a.add && b.mou && a.suf < b.pre) ||
(a.mou && b.sub && a.suf > b.pre) )
c.mou = 1;
if(a.len == 1) c.mou = a.suf < b.pre && (b.mou || b.sub);
if(b.len == 1) c.mou = a.suf > b.pre && (a.mou || a.add);
}
else c.mou = 0;
c.pre = a.pre, c.suf = b.suf;
return c;
}
注意查询时的的信息返回也是一大坑点， 访问到空区间时的相关参数赋值(死了一个小时多没想出来，赛后多亏仙佬指点)，这里不要用普通的那样查询，按整个区间块返回合并，题解也是这样，避免了大量空区间的参数定义，详情看代码。注意操作一有区间操作，别忘了下传
lazy标记。
#include<bits/stdc++.h>
#define int long long
using namespace std;
using ull = unsigned long long;
using ll = long long;
using PII = pair<ll,ll>;
using PIII = pair<ll, pair<ll,ll>>;
#define endl "\n"
#define pb push_back
#define IOS ios::sync_with_stdio(false);cin.tie(0)
#define lowbit(x) (x) & (-x)
#define point(x) setiosflags(ios::fixed)<<setprecision(x)
const int N=1e5+10;
const int INF=0x3f3f3f3f;
const int mod=1e9+7;
struct Info {//一定要初始化
int pre, suf;//区间最前面一个，最后一个，
int len = 1;
int lazy;
int add, sub, mou;//是否是递增，递减，单峰
int same;//是否是相同
Info (int x) {
pre = suf = x;
lazy = 0;
add = sub = same = 1;
mou = 0;
}
Info () {
pre = -1e18, suf = -1e18;
lazy = 0;
add = sub = same = 1;
mou = 0;
}
};
Info merge(const Info& a, const Info& b) {
Info c;
if(a.same && b.same && a.suf == b.pre) c.same = 1;
else c.same = 0;
if(a.add && b.add && a.suf < b.pre) c.add = 1;
else c.add = 0;
if(a.sub && b.sub && a.suf > b.pre) c.sub = 1;
else c.sub = 0;
c.len = a.len + b.len;
if(c.len >= 3) {
if((a.add && b.sub) ||
(a.add && b.mou && a.suf < b.pre) ||
(a.mou && b.sub && a.suf > b.pre) )
c.mou = 1;
if(a.len == 1) c.mou = a.suf < b.pre && (b.mou || b.sub);
if(b.len == 1) c.mou = a.suf > b.pre && (a.mou || a.add);
}
else c.mou = 0;
c.pre = a.pre, c.suf = b.suf;
return c;
}
struct segtree {
#define ls (u << 1)
#define rs (u << 1 | 1)
int n;
segtree(int n) {init(n);};
vector<Info> info;
vector<int> a;
void init(int n) {
this->n = n;
info.resize(n << 2);
a.resize(n << 1);
}
void push_up(int u) {
info[u] = merge(info[ls], info[rs]);
}
void build(int u, int l, int r)
{
if(l == r)
{
info[u] = Info();//填值
return ;
}
int mid = l + r >> 1;
build(u << 1, l, mid);
build(u << 1 | 1, mid + 1, r);
push_up(u);
}
void settag(int u, int k) {//处理数据
info[u].pre += k;
info[u].suf += k;
info[u].lazy += k;
}
void push_down(int u)
{
if(info[u].lazy)
{
settag(ls, info[u].lazy);
settag(rs, info[u].lazy);
info[u].lazy = 0;
}
}
void update(int u, int l, int r, int pos, int k) {
if(l == r) {
info[u] = Info(k);
return;
}
push_down(u);
int mid = l + r >> 1;
if(pos <= mid) update(ls, l, mid, pos, k);
else update(rs, mid + 1, r, pos, k);
push_up(u);
};
void update(int u, int l, int r, int x, int y, int k) {
if(x <= l && r <= y) {
settag(u, k);
return;
}
push_down(u);
int mid = l + r >> 1;
if(x <= mid) update(ls, l, mid, x, y, k);
if(mid < y) update(rs, mid + 1, r, x, y, k);
push_up(u);
}
void update(int pos, int v) {
update(1, 1, n, pos, v);
}
void update(int x, int y, int k) {
update(1, 1, n, x, y, k);
}
Info query(int u, int l, int r, int x, int y) {
if (x <= l && r <= y) return info[u];
push_down(u);
int mid = l + r >> 1;
if (y <= mid) return query(ls, l, mid, x, y);
else if (mid < x) return query(rs, mid + 1, r, x, y);
else return merge(query(ls, l, mid, x, y), query(rs, mid + 1, r, x, y));
}
Info query(int l, int r) {
return query(1, 1, n, l, r);
}
};
void solve(){
int n; cin >> n;
segtree tr(n);
for(int i = 1; i <= n; i ++) {
int x; cin >> x;
tr.update(i, x);
}
int m; cin >> m;
while(m --) {
int op, l, r; cin >> op >> l >> r;
ll x;
if(op == 1) {
cin >> x;
tr.update(l, r, x);
}
else if(op == 2) {
auto t = tr.query(l, r);
cout << t.same << endl;
}
else if(op == 3) {
auto t = tr.query(l, r);
cout << t.add << endl;
}
else if(op == 4) {
auto t = tr.query(l, r);
cout << t.sub << endl;
}
else if(op == 5) {
auto t = tr.query(l, r);
cout << t.mou << endl;
}
}
}
signed main()
{
IOS;
int T = 1;
//cin>>T;
while(T--)
{
solve();
}
return 0;
}