题意
给定一个数列，每次查询一个区间，和一个值h，问区间内有多少个数小于等于h。
分析
二分数的个数，划分树求解判断是否满足条件，划分树求解的是第k小的数，那么前面k个数肯定不大于这个数了，比较这个数和h即可。
code
#include#include #include #include using namespace std;typedef long long ll;const int INF = 1e9;const int MAXN = 1e5 + 5;const int LOG_N = 30;// tree[dep][i] 第dep层第i个位置的数值int tree[LOG_N][MAXN];int sorted[MAXN];// toleft[p][i] 第p层前i个数中有多少个整数分入下一层int toleft[LOG_N][MAXN];void build(int l, int r, int dep){ if(l == r) return; int mid = (l + r) / 2; int same = mid - l + 1; // 和中点数相同的数的个数 for(int i = l; i <= r; i++) if(tree[dep][i] < sorted[mid]) same--; int lpos = l, rpos = mid + 1; for(int i = l; i <= r; i++) { if(tree[dep][i] < sorted[mid]) tree[dep + 1][lpos++] = tree[dep][i]; else if(tree[dep][i] == sorted[mid] && same) { tree[dep + 1][lpos++] = tree[dep][i]; same--; } else tree[dep + 1][rpos++] = tree[dep][i]; toleft[dep][i] = toleft[dep][l - 1] + lpos - l; } build(l, mid, dep + 1); build(mid + 1, r, dep + 1);}// [L,R]里查询子区间[l,r]第k小的数int query(int L, int R, int l, int r, int dep, int k){ if(l == r) return tree[dep][l]; int mid = (L + R) / 2; // 有多少个查询区间内的节点会进入下一层的左子树 int cnt = toleft[dep][r] - toleft[dep][l - 1]; if(cnt >= k) { int newl = L + toleft[dep][l - 1] - toleft[dep][L - 1]; int newr = newl + cnt - 1; return query(L, mid, newl, newr, dep + 1, k); } else { int newr = r + toleft[dep][R] - toleft[dep][r]; int newl = newr - (r - l - cnt); return query(mid + 1, R, newl, newr, dep + 1, k - cnt); }}int n, m;int solve(int s, int t, int h){ int l = 1, r = (t - s) + 1, mid; int ans = 0; while(l <= r) { mid = (l + r) / 2; if(query(1, n, s, t, 0, mid) <= h) { ans = mid; l = mid + 1; } else r = mid - 1; } return ans;}int main(){ int T; scanf("%d", &T); for(int kase = 1; kase <= T; kase++) { scanf("%d%d", &n, &m); for(int i = 1; i <= n; i++) { scanf("%d", &sorted[i]); tree[0][i] = sorted[i]; } sort(sorted + 1, sorted + n + 1); build(1, n, 0); printf("Case %d:\n", kase); while(m--) { int s, t, h; scanf("%d%d%d", &s, &t, &h); s++; t++; printf("%d\n", solve(s, t, h)); } } return 0;}