http://acm.hdu.edu.cn/showproblem.php?pid=4417
题意：
给定一个长度为n的序列，求区间[L,R]中小于h的个数；
思路：
分三种情况：
1：如果该区间最小值都大于h输出0；
2：如果该区间最大值小于等于h输出区间长度：
3：否则，二分枚举该区间的第m大，直到找到第m大为最后一个小于等于h的；
View Code #include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <cmath> #include <queue> #include <stack> #include <set> #include <map> #include <string>#define CL(a,num) memset((a),(num),sizeof(a)) #define iabs(x) ((x) > 0 ? (x) : -(x)) #define Min(a , b) ((a) < (b) ? (a) : (b)) #define Max(a , b) ((a) > (b) ? (a) : (b))#define ll __int64 #define inf 0x7f7f7f7f #define MOD 100000007 #define lc l,m,rt<<1 #define rc m + 1,r,rt<<1|1 #define pi acos(-1.0) #define test puts("<------------------->") #define maxn 100007 #define M 100007 #define N 100007 using namespace std; //freopen("din.txt","r",stdin); struct node{int l,r;int mid(){return (l + r)>>1;} }tt[N<<2];int toLeft[20][N],val[20][N]; int sorted[N]; int n,m; int MIN,MAX;void build(int l,int r,int rt,int d){int i;tt[rt].l = l;tt[rt].r = r;if (l == r) return ;int m = tt[rt].mid();int lsame = m - l + 1;for (i = l; i <= r; ++i){if (val[d][i] < sorted[m]) lsame--;}int lpos = l,rpos = m + 1;int same = 0;for (i = l; i <= r; ++i){if (i == l) toLeft[d][i] = 0;else toLeft[d][i] = toLeft[d][i - 1];if (val[d][i] < sorted[m]){toLeft[d][i]++;val[d + 1][lpos++] = val[d][i];}else if (val[d][i] > sorted[m]){val[d + 1][rpos++] = val[d][i];}else{if (same < lsame){same++;val[d + 1][lpos++] = val[d][i];toLeft[d][i]++;}else{val[d + 1][rpos++] = val[d][i];}}}build(lc,d + 1);build(rc,d + 1); } int query(int L,int R,int k,int d,int rt){if (L == R) return val[d][L];int s,ss;if (L == tt[rt].l){ss = 0;s = toLeft[d][R];}else{ss = toLeft[d][L - 1];s = toLeft[d][R] - toLeft[d][L - 1];}if (s >= k){int newl = tt[rt].l + ss;int newr = newl + s - 1;return query(newl,newr,k,d + 1,rt<<1);}else{int m = tt[rt].mid();int bb = L - tt[rt].l - ss;int b = R - L + 1 - s;int newl = m + bb + 1;int newr = newl + b - 1;return query(newl,newr,k - s,d + 1,rt<<1|1);} } int bSearch(int l,int r,int h,int x,int y){int ans = 0;while (l <= r){int m = (l + r)>>1;if (query(x,y,m,0,1) > h)r = m - 1;else{l = m + 1;ans = m;}}return ans; } int Input(){char ch = getchar();while (ch < '0' || ch > '9') ch = getchar();int num = 0;while (ch >= '0' && ch <= '9'){num = num*10 + ch - '0';ch = getchar();}return num; } int main(){//freopen("din.txt","r",stdin);int t,i;int x,y,h;int cas = 1;t = Input();while (t--){printf("Case %d:\n",cas++);n = Input();m = Input();for (i = 1; i <= n; ++i){val[0][i] = Input();sorted[i] = val[0][i];}sort(sorted + 1,sorted + 1 + n);build(1,n,1,0);while (m--){x = Input();y = Input();h = Input();x++; y++;MIN = 1;MAX = y - x + 1;if (query(x,y,MIN,0,1) > h) puts("0");else if (query(x,y,MAX,0,1) <= h) printf("%d\n",MAX);else{int pos = bSearch(MIN,MAX,h,x,y);printf("%d\n",pos);}}}return 0; }