划分树。
题意是，给一个长度为n的数组，之后有m次询问，每次询问为三元组（l,r,k），问数组中第l到第r个元素间第k小的元素是什么。
又是一题很有意思的题目，常规解法的时间复杂度在这里是完全不可行的，必须预先建树后才能O(lgN)地回答每次询问。但看了划分树的建树思想后还是推了很久。
划分树是基于线段树的，其基本思想在于父节点上[L,R]区间上[l,r]中的第k小元素，如何O(1）时间地递推到左子树或右子树中，这样总共O(lgN)次后便能得到答案。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 |
#include<cstring> #include<cstdio> #include<algorithm> using namespace std; int n,m,a[100000],b[100000],sa[100000],el[2000000],ml,ell; struct node { int s; node *l,*r; }mem[2000000],*root; void init(int L,int R,node *p) { int m=L+R>>1,e=0,i,j,k; p->s=ell; for(i=L;i<=R;i++) { e+=a[i]<=sa[m]?1:0; el[ell++]=e; } for(i=j=L,k=m+1;i<=R;i++) { if(a[i]<=sa[m]) b[j++]=a[i]; else b[k++]=a[i]; } memcpy(a+L,b+L,4*(R-L+1)); if(L==R) return; p->l=&mem[ml++]; p->r=&mem[ml++]; init(L,m,p->l); init(m+1,R,p->r); } inline int calc(int l,int r,int k) { int m,L=0,R=n-1,f; node *p=root; while(L!=R) { m=L+R>>1; if(!l) f=el[p->s+r]; else f=el[p->s+r]-el[p->s+l-1]; if(k<=f) { if(l) l=el[p->s+l-1]; r=el[p->s+r]-1; p=p->l; R=m; } else { k-=f; if(l) l=l-el[p->s+l-1]; r=r-el[p->s+r]; p=p->r; L=m+1; } } return sa[L]; } int main() { int i,j,k; while(~scanf("%d%d",&n,&m)) { ml=ell=0; root=&mem[ml++]; for(i=0;i<n;i++) { scanf("%d",&a[i]); sa[i]=a[i]; } sort(sa,sa+n); init(0,n-1,root); while(m--) { scanf("%d%d%d",&i,&j,&k); printf("%d\n",calc(i-1,j-1,k)); } } return 0; } |