在给定\(N\)长的数组 \({A}\) 中进行 \(Q\) 次询问 \([L_i,R_i]\) 区间中不大于 \(H_i\) 的元素个数。
共包含 \(T\) 组数据。
题目中各个询问之间毫无关系,故可以考虑离线的做法。
对于一个区间 \([l, r]\) 中不大于 \(h_i\)的元素个数可以采用前缀和的思想来处理: 即我们用 \(F(x)\)表示 \([1, x]\)中不大于 \(h_i\) 的元素个数,所以答案即为: \(F(r) - F(l - 1)\).
然后如何求出每个 \(F\),我们可以使用权值线段树或者树状数组来维护从 \(1\) 到 \(n\) 的每个位置上的关于 \(h\) 的关系。
具体思路是我们对于每个询问,都把 \(h_i\) 存于对应的 \(l - 1\) 和 \(r\) 中,之后遍历每个位置,对于每一个位置\(i\),我们使用树状数组把 \(a[i]\) 处置 \(1\),同时对于这一位置上存储的所有 \(h_i\),都通过树状数组的询问操作得出对应 \(h\) 的 \(F\)值。最后再次遍历一遍每个询问,\(F(r_i) - F(l_i - 1)\) 得出答案即可。
#include <bits/stdc++.h> using namespace std; const int N = 1e5 + 7; int n,q; int a[N]; struct $ { int l,r,h; bool operator <(const $ p)const{ return h < p.h; } }b[N]; vector<$>v[N]; pair<int,int>c[N]; int tree[N * 4]; void add(int x, int m) { for (; x <= m; x += x& -x) tree[x] ++; } int ask(int x) { int ret = 0; for (; x; x -= x & -x) { ret += tree[x]; } return ret; } void solve() { map<int,int>mp; int cnt = 0; cin >> n >> q; set<int>s; for (int i = 1; i <= n; i++) { scanf("%d", &a[i]); s.insert(a[i]); } for (int i = 1; i <= q; i++) { scanf("%d%d%d", &b[i].l, &b[i].r, &b[i].h); s.insert(b[i].h); v[b[i].l - 1].push_back(($){0, b[i].h, i}); v[b[i].r].push_back(($){1, b[i].h, i}); } int m = s.size(); for (int i : s) mp[i] = ++cnt; for (int i = 0; i <= n; i++) { if (i) add(mp[a[i]], m); for (auto p : v[i]) { int f = p.l; int j = mp[p.r]; int idx = p.h; int k = ask(j); if (f) c[idx].second = k; else c[idx].first = k; } } for (int i = 1; i <= q; i++) { printf("%d ", c[i].second - c[i].first); } puts(""); for (int i = 0; i <= m; i++) tree[i] = 0; for (int i = 0; i <= n; i++) v[i].clear(); } int main() { int T; cin >> T; while (T--) solve(); return 0; }