P9912 [COCI 2023/2024 #2] Zatopljenje - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
线段树。
离线处理询问，将询问的高度从大到小排序，每次往线段树中加入高度大于当前询问高度的点，然后做一遍区间连续段个数就可以了。code：
#include <bits/stdc++.h>
using namespace std;
const int N = 200010;
int n, q; struct Node { int id, h; } a[N];
struct Questions {
int l, r, h, id, ans;
} b[N];
struct SgT {
int res;
bool l1, r1;
SgT() {res = l1 = r1 = 0;}
} T[N * 4];
#define ls(k) (k << 1)
#define rs(k) (k << 1 | 1)
void pushup(SgT& a, SgT son1, SgT son2) {
a.res = son1.res + son2.res - (son1.r1 && son2.l1);
a.l1 = son1.l1, a.r1 = son2.r1;
}
void update(int l, int r, int k, int x) {
if(l == r) {
T[k].l1 = T[k].r1 = 1, T[k].res = 1;
return;
} int mid = (l + r) / 2;
if(x <= mid) update(l, mid, ls(k), x);
else update(mid + 1, r, rs(k), x);
pushup(T[k], T[ls(k)], T[rs(k)]);
}
SgT query(int l, int r, int k, int L, int R) {
if(L <= l && r <= R) return T[k];
int mid = (l + r) / 2; SgT son1, son2; bool b1 = 0, b2 = 0;
if(L <= mid) son1 = query(l, mid, ls(k), L, R), b1 = 1;
if(mid < R) son2 = query(mid + 1, r, rs(k), L, R), b2 = 1;
if(b1 and b2) {
SgT res; pushup(res, son1, son2);
return res;
} else if(b1) return son1;
else return son2;
}
int main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin >> n >> q;
for (int i = 1; i <= n; i++) cin >> a[i].h, a[i].id = i;
sort(a + 1, a + 1 + n, [](Node x, Node y) {return x.h > y.h;});
for (int i = 1; i <= q; i++) cin >> b[i].l >> b[i].r >> b[i].h, b[i].id = i;
sort(b + 1, b + 1 + q, [](Questions x, Questions y) {return x.h > y.h;});
int pos = 1;
for (int i = 1; i <= q; i++) {
while(a[pos].h > b[i].h) update(1, n, 1, a[pos].id), pos++;
b[i].ans = query(1, n, 1, b[i].l, b[i].r).res;
}
sort(b + 1, b + 1 + q, [](Questions x, Questions y){return x.id < y.id;});
for (int i = 1; i <= q; i++) cout << b[i].ans << '\n';
return 0;
}