洛谷 P9912 Zatopljenje
题意
给出长度为 \(n\) 的序列 \(a\)，有 \(q\) 次询问。
每次给出 \(l,r,x\)，询问区间 \([l,r]\) 中有多少段极长的，\(a\) 都大于 \(x\) 的段。
思路
离线后扫描线。
先把询问和 \(a\) 离散化，然后扫描 \(a\) 的值。
维护序列 \(b\)，初始全为 \(1\)。
扫描从 \(0\) 到离散化后的最大值，
扫描到一个值 \(v\) 时，对于所有 \(i(a_i=v)\)，将 \(b_i \leftarrow 0\)。
同时处理所有 \(x=v\) 的询问，即查询 \(b\) 中区间内有多少段连续的 \(1\)。
单点修改，区间查询，可使用线段树维护。
时间复杂度：\(O(n \log n)\)。
代码
#include <bits/stdc++.h>
using namespace std;
const int N = 5e5 + 5;
struct segt {
struct node {
int l, r;
int left, right;
int cnt;
} t[N << 2];
#define ls (p << 1)
#define rs (p << 1 | 1)
friend node operator + (node a, node b) {
node res; res.l = a.l, res.r = b.r;
if (a.cnt && b.cnt) {
res.left = a.left, res.right = b.right;
res.cnt = a.cnt + b.cnt;
if (a.right + 1 == b.left) res.cnt --;
} else if (a.cnt) {
res.left = a.left, res.right = a.right;
res.cnt = a.cnt;
} else if (b.cnt) {
res.left = b.left, res.right = b.right;
res.cnt = b.cnt;
} else {
res.left = -1, res.right = -1;
res.cnt = 0;
}
return res;
}
void build(int p, int l, int r, int* a) {
if (l == r) {
t[p] = {l, r, l, r, 1};
return ;
}
int mid = (l + r) >> 1;
build(ls, l, mid, a);
build(rs, mid + 1, r, a);
t[p] = t[ls] + t[rs];
}
void del(int p, int id) {
if (t[p].l == t[p].r) {
t[p] = {t[p].l, t[p].r, -1, -1, 0};
return ;
}
if (id <= t[ls].r) del(ls, id);
else del(rs, id);
t[p] = t[ls] + t[rs];
}
node query(int p, int l, int r) {
if (l <= t[p].l && t[p].r <= r) return t[p];
node res; res.l = -1;
if (t[ls].r >= l) res = query(ls, l, r);
if (t[rs].l <= r) {
if (res.l == -1) res = query(rs, l, r);
else res = res + query(rs, l, r);
}
return res;
}
} T;
struct Query {int l, r, h, id;};
int n, q, a[N], b[N], tot, ans[N];
Query Q[N];
vector <int> M[N], OP[N];
int main() {
scanf("%d%d", &n, &q);
for (int i = 1; i <= n; i ++) {
scanf("%d", &a[i]);
b[++ tot] = a[i];
}
for (int i = 1; i <= q; i ++) {
scanf("%d%d%d", &Q[i].l, &Q[i].r, &Q[i].h);
b[++ tot] = Q[i].h, Q[i].id = i;
}
b[++ tot] = 0;
sort(b + 1, b + tot + 1);
tot = unique(b + 1, b + tot + 1) - b - 1;
for (int i = 1; i <= n; i ++) {
a[i] = lower_bound(b + 1, b + tot + 1, a[i]) - b;
M[a[i]].push_back(i);
}
for (int i = 1; i <= q; i ++) {
Q[i].h = lower_bound(b + 1, b + tot + 1, Q[i].h) - b;
OP[Q[i].h].push_back(i);
}
T.build(1, 1, n, a);
for (int i = 1; i <= tot; i ++) {
for (auto v : M[i]) T.del(1, v);
for (auto v : OP[i]) {
auto op = Q[v];
auto res = T.query(1, op.l, op.r);
ans[op.id] = res.cnt;
}
}
for (int i = 1; i <= q; i ++) printf("%d\n", ans[i]);
return 0;
}