本文共 1997 字，大约阅读时间需要 6 分钟。
第一次 耍划分树。。
。
模板是找第ｋ小的
#include #include #include #include #include #include #include using namespace std;#include #include #include #include #include #include typedef long long LL;const int MAXN = 100999;//点数的最大值const int MAXM = 1000010;//边数的最大值const LL INF = 1152921504;/** 划分树(查询区间第k小)*/int tree[20][MAXN];//表示每层每一个位置的值int sorted[MAXN];//已经排序好的数int toleft[20][MAXN];//toleft[p][i]表示第p层从1到i有数分入左边void build(int l,int r,int dep){ if(l == r)return; int mid = (l+r)>>1; int same = mid - l + 1;//表示等于中间值并且被分入左边的个数 for(int i = l; i <= r; i++) //注意是l,不是one if(tree[dep][i] < sorted[mid]) same--; int lpos = l; int 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 > 0) { 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);}//查询区间第k小的数,[L,R]是大区间,[l,r]是要查询的小区间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)>>1; 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 main(){ int n,m,t,cas=1; // freopen("in.txt","r",stdin); scanf("%d",&t); while(t--) { scanf("%d%d",&n,&m); memset(tree,0,sizeof(tree)); for(int i = 1; i <= n; i++) { scanf("%d",&tree[0][i]); sorted[i] = tree[0][i]; } sort(sorted+1,sorted+n+1); build(1,n,0); int l,r,num; printf("Case %d:\n",cas++); while(m--) { scanf("%d%d%d",&l,&r,&num); l++,r++; int y=r-l+1,z=1;//边界 while(z<=y) { int x=(z+y)>>1; int sum=query(1,n,l,r,0,x); if(sum<=num) z=x+1; else y=x-1; } z=r-l+1-z+1; printf("%d\n",r-l+1-z); } } return 0;}
转载地址：http://cufxa.baihongyu.com/