题意：给一个长度n的数列和m次查询（l，r，h），求区间[l，r]内小于等于h的元素个数。
思路：可以用划分树求区间内第k小数，然后二分k，根据k查询到不大于h的最大值，此时k就是结果。
#include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<cstdlib> #include<vector> #include<map> #include<algorithm> using namespace std; typedef long long ll; const int inf = 0x3f3f3f3f; const int mod = 1000000007; const int maxn=100005; int tree[20][maxn], toLeft[20][maxn], sorted[maxn]; void build(int level, int l, int r){//建树 if(l == r)return; int mid = (l + r) >> 1; int cnt = mid - l + 1; for(int i=l; i<=r; ++i){ if(tree[level][i] < sorted[mid]){ --cnt; } } int lpos = l, rpos = mid + 1; for(int i=l; i<=r; ++i){ if(i == l){ toLeft[level][i] = 0; } else { toLeft[level][i] = toLeft[level][i - 1]; } if(tree[level][i] < sorted[mid]){ tree[level + 1][lpos++] = tree[level][i]; ++toLeft[level][i]; } else if(tree[level][i] > sorted[mid]) { tree[level + 1][rpos++] = tree[level][i]; } else { if(cnt){ tree[level + 1][lpos++] = tree[level][i]; ++toLeft[level][i]; --cnt; } else { tree[level + 1][rpos++] = tree[level][i]; } } } build(level + 1, l, mid); build(level + 1, mid + 1, r); } int query(int level, int l, int r, int ql, int qr, int k){//查询 //当前层次、当前区间左右边界、查询区间左右边界、查询第k小值 if(ql == qr){ return tree[level][ql]; } int s1 = (l == ql ? 0 : toLeft[level][ql - 1]); int s2 = toLeft[level][qr] - s1; int mid = (l + r) >> 1; if(s2 >= k){ return query(level + 1, l, mid, l + s1, l + s1 + s2 - 1, k); } else { return query(level + 1, mid + 1, r, mid + ql - l - s1 + 1, mid - l + qr - s1 - s2 + 1, k - s2); } } int main(){ int n, m, L, R, k, H, t, cas = 0; scanf("%d", &t); while(t--){ scanf("%d%d", &n, &m); for(int i=1; i<=n; ++i){ scanf("%d", &tree[0][ i]); sorted[i] = tree[0][i]; } sort(sorted + 1, sorted + n + 1); build(0, 1, n); printf("Case %d:\n", ++cas); while(m--){ scanf("%d%d%d", &L, &R, &H); int l = 0, r = R - L + 2; while(r - l > 1){//二分答案 int mid = (l + r) >> 1; if(query(0, 1, n, L + 1, R + 1, mid) <= H){ l = mid; } else { r = mid; } } printf("%d\n", l); } } return 0; }
