题意：有n个数，m个询问（l，r，k），问在区间[l,r] 有多少个数小于等于k。
划分树――查找区间第k大的数。。。。
利用划分树的性质，二分查找在区间[l,r]小于等于k的个数。
如果在区间第 i 大的数tmp>k,则往下找，如果tmp
#include #include #include #include #include #include #include #include #include #include #include using namespace std; #define INF 1e8 #define eps 1e-8 #define LL long long #define N 100010 #define mod 1000000007 int a[N],s[N],t[20][N],num[20][N],n,m; void build(int c,int l,int r) { if(l==r) return; int mid=(l+r)/2; int lm=mid-l+1,lp=l,rp=mid+1; for(int i=l;i<=r;i++) lm-=s[i] k) puts("0"); else { int ll=0,rr=r-l+1,mid; while(ll<=rr) { mid=(ll+rr)>>1; int tmp=query(0,1,n,l,r,mid);//如果在区间[l,r]第mid大的数大于k，rr=mid-1 if(tmp>k) rr=mid-1; else ll=mid+1;//否则ll=mid+1 } printf("%d\n",ll-1); } } } return 0; } /* 1 10 10 0 5 2 7 5 4 3 8 7 7 2 8 6 3 5 0 1 3 1 1 9 4 0 1 0 3 5 5 5 5 1 4 6 3 1 5 7 5 7 3 */