首先发现区间中的个数等于 \(\texttt{高度大于 x 的位置的个数} - \texttt{连续两个位置都是大于 x 的位置的个数}\)。具体令 \(H_i = \min(h_i, h_{i+1}) (i \in [1, n-1])\)，那么对于一次询问答案 \(ans=\sum\limits_{i=l}^{r}[h_i > x] - \sum\limits_{i=l}^{r-1}[H_i > x]\)，其中 \([a > b]\) 表示当 \(a > b\) 时为 \(1\)，反之为 \(0\)。特别地，对于 \(l=r\) 的情况，答案就是 \([h_i > x]\)。
证明：一个岛屿一定是由一段连续的高度大于 \(x\) 的位置组成，那么这一段连续两个位置都是大于 \(x\) 的位置的个数正好是这一段区间的长度减一（可以想象这一段区间有多少个间隔，显然是区间长度减一），那么两者相减就是 \(1\) ，求和之后就算出了 \(1\) 的个数，也就是岛屿的个数。证毕。
很明显，原问题成了两个数组中区间内大于某个数的个数，具体来讲，就是 \(h_l \sim h_r\) 大于 \(x\) 的个数减去 \(H_l \sim H_{r-1}\) 大于 \(x\) 的个数。使用分块是个做法，但是由于 不能过这道题 我们要学习更优的 \(\log\) 的算法，有以下两种解法。
离线使用线段树
考虑对原问题离线，将 \([l, r]\) 的询问拆成 \([1, r]\) 的询问减去 \([1, l-1]\) 的询问，这样从左到右扫一遍，同时维护一个数据结构能快速求得目前比 \(x\) 大的个数。离散化使用树状数组是一种方法，或者直接使用权值线段树。
时间复杂度为 \(\Theta((n+q)\log n)\) 以及一个线段树不小的常数？ 。
具体实现如下：
#include <cstdio>
#include <vector>
using namespace std;
int n, q, h[200010], H[200010], ans[200010];
struct node{ int f, idx, x; };
vector<node> qry1[200010], qry2[200010];
const int inf = 1000000000;
struct Segment_Tree{
struct node{ int lson, rson, sum; };
node tree[1000010 << 2];
int tot, root;
void pushup(int idx){ tree[idx].sum = tree[tree[idx].lson].sum + tree[tree[idx].rson].sum; }
int query(int &idx, int trl, int trr, int l, int r){
if (!idx || trl > r || trr < l) return 0;
if (l <= trl && trr <= r) return tree[idx].sum;
int mid = (trl + trr) >> 1;
return query(tree[idx].lson, trl, mid, l, r) + query(tree[idx].rson, mid + 1, trr, l, r);
}
void modify(int &idx, int trl, int trr, int p, int v){
if (trl > p || trr < p) return;
if (!idx) idx = ++tot, tree[idx] = {0, 0, 0};
if (trl == trr) return tree[idx].sum += v, void();
int mid = (trl + trr) >> 1; modify(tree[idx].lson, trl, mid, p, v), modify(tree[idx].rson, mid + 1, trr, p, v), pushup(idx);
} void clear(){ tot = 0, root = 0; }
} yzh;
signed main(){
scanf("%d%d", &n, &q);
for (int i=1;i<=n;++i) scanf("%d", &h[i]), H[i-1] = min(h[i-1], h[i]);
for (int i=1;i<=q;++i){
int l, r, x; scanf("%d%d%d", &l, &r, &x);
if (l == r) ans[i] = h[l] > x;
else {
qry1[r].push_back({1, i, x}), qry1[l-1].push_back({-1, i, x});
qry2[l-1].push_back({1, i, x}), qry2[r-1].push_back({-1, i, x});
}
} for (int i=1;i<=n;++i){
yzh.modify(yzh.root, 0, inf, h[i], 1);
for (auto [f, idx, x]:qry1[i]) ans[idx] += f * yzh.query(yzh.root, 0, inf, x + 1, inf);
} yzh.clear();
for (int i=1;i<=n-1;++i){
yzh.modify(yzh.root, 0, inf, H[i], 1);
for (auto [f, idx, x]:qry2[i]) ans[idx] += f * yzh.query(yzh.root, 0, inf, x + 1, inf);
} for (int i=1;i<=q;++i) printf("%d\n", ans[i]);
return 0;
}
直接使用主席树
其实可以考虑使用可持久化的数据结构（主席树），这样可以在线解决，万一题目强制在线，那么离线的全都挂掉了。剩下的就是板子了。具体地，我们讲所有高度离散化，主席树里面存值域区间出现的数字个数。对于询问，我们在离散化之前所有高度中找到最后一个小于等于 \(x\) 的高度（由于离散化要先排序，这一步可以用 upper_bound 二分，对时间复杂度没有影响），令这个高度为 \(h_0\)，那么就查询 \(l \sim r\) 中大于 \(h_0\) 的个数即可。
时间复杂度：\(\Theta((n+q)\log n)\)。
放上代码。
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
int n, q, h[200010], real[200010], V;
struct Yzh_Is_The_President{
struct node{
int lson, rson;
int val;
} tree[200010 * 4 + 200010 * 20];
int root[200010 * 4 + 200010 * 20], tot;
void pushup(int idx){
tree[idx].val = tree[tree[idx].lson].val + tree[tree[idx].rson].val;
}
void build(int &idx, int l, int r){
tree[idx = ++tot] = {0, 0, 0};
if (l == r) return;
int mid = (l + r) >> 1;
build(tree[idx].lson, l, mid), build(tree[idx].rson, mid + 1, r);
}
void modify(int &idx, int oidx, int trl, int trr, int p, int v){
if (trl > p || trr < p) return;
tree[idx = ++tot] = tree[oidx];
if (trl == trr) return tree[idx].val += v, void();
int mid = (trl + trr) >> 1;
modify(tree[idx].lson, tree[oidx].lson, trl, mid, p, v);
modify(tree[idx].rson, tree[oidx].rson, mid + 1, trr, p, v);
pushup(idx);
}
int query(int lidx, int ridx, int trl, int trr, int l, int r){
if (trl > r || trr < l) return 0;
if (l <= trl && trr <= r) return tree[ridx].val - tree[lidx].val;
int mid = (trl + trr) >> 1;
return query(tree[lidx].lson, tree[ridx].lson, trl, mid, l, r) +
query(tree[lidx].rson, tree[ridx].rson, mid + 1, trr, l, r);
}
} xym, yzh;
signed main() {
scanf("%d%d", &n, &q);
for (int i = 1; i <= n; ++i) scanf("%d", &h[i]), real[i] = h[i];
sort(real + 1, real + n + 1);
V = unique(real + 1, real + n + 1) - real - 1;
for (int i = 1; i <= n; ++i) h[i] = lower_bound(real + 1, real + V + 1, h[i]) - real;
xym.build(xym.root[0], 1, V), yzh.build(yzh.root[0], 1, V);
for (int i = 1; i <= n; ++i) xym.modify(xym.root[i], xym.root[i - 1], 1, V, h[i], 1);
for (int i = 1; i <= n - 1; ++i) yzh.modify(yzh.root[i], yzh.root[i - 1], 1, V, min(h[i], h[i + 1]), 1);
for (int i = 1; i <= q; ++i) {
int l, r, x;
scanf("%d%d%d", &l, &r, &x);
if (l == r)
printf("%d\n", real[h[l]] > x);
else if (x < real[1])
puts("1");
else {
int v = upper_bound(real + 1, real + V + 1, x) - real - 1;
printf("%d\n", xym.query(xym.root[l - 1], xym.root[r], 1, V, v + 1, V) - yzh.query(yzh.root[l - 1], yzh.root[r - 1], 1, V, v + 1, V));
}
}
return 0;
}