3946. K-th Number - #include <Seter> - using namespace Orz;
3946. K-th Number
http://www.spoj.pl/problems/MKTHNUM/
| ID | DATE | USER | RESULT | TIME | MEM | LANG |
|---|---|---|---|---|---|---|
| 5779384 | 2011-10-05 04:49:51 | Seter |
accepted edit run |
2.54 | 9.8M |
C |
查询区间K大数……很久以前就想做了一直懒得看……前几天吃饭的时候突然弄懂了划分树然后自己YY了一个！结果在SPOJ跑了第二，POJ跑了第N……好囧啊
果然是大牛都去做POJ了么……
划分树是这样的：假设原序列是A，排序后序列是RANK。试想一个线段树，每条线段[L,R]保存的是RANK[L..R]这些数在A中的顺序。然后再保存一个f[logn][n]，记录第i层第j个数所在的这条线段中，第j个数左边（包括第j个）有几个数在下一层被分到左边。举个例子：
线段树（左边n/2个，右边(n+1)/2个，红色的是上一层中被分到左边的）：
| 5 | 2 | 1 | 3 | 2 |
| 2 | 1 | 5 | 3 | 2 |
| 1 | 2 | 2 | 5 | 3 |
| 3 | 5 |
f数组：
| 0 | 1 | 2 | 2 | 2 |
| 0 | 1 | 0 | 0 | 1 |
| 0 | 1 |
先来解决ASK的问题：在第I层的某条线段[L,R]中的区间[NL,NR]找KTHNUM时如何向下转移。
首先我们需要知道KTHNUM被分到左边还是右边，容易得出[NL,NR]中分到左边的数字个数大于等于K时KTHNUM在左边，即F[I][NR]-F[I][NL-1]。如果一个数字被分到左边，那么NL=F[I][NL-1]，NR变成F[I][NR]-1，K不变。分到右边的情况稍复杂，大家可以自己推算一下。
那么如何构造线段树与F数组呢？首先注意到RANK数组是不变得，所以对于线段[L,R]中位数MID就是RANK[(L+R)/2]。由于MID可能出现多次，其中一些在左边一些在右边，所以必须先遍历一遍RANK[L..R]，求出有多少数小于MID。构造下一层时，如果一个数在左边，那么F[I][J]=F[I][J-1]+1，否则F[I][J]=F[I][J-1]。递归构树。
很简单罢！然后很容易发现线段树那个数组是可以滚动的（由于在ASK时可以完全甩掉线段树）……于是乎，滚乎！即ASK时只需要知道F数组就可以了。
这次先上代码再来解释一下其余方法，40行不到，不长不短，最难写的ASK又很容易调试，一般过了5组数据就说明对了：
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 | #include <stdio.h>#include <stdlib.h>int f[18][100000],n,m,a[2][100000],rank[100000];cmp(const void *a,const void *b){return *(int*)a-*(int*)b;}inline void make(_Bool c,int d,int s,int l){ int i=-1,x=l>>1,mid=rank[s+x],p=0,*nl=a[!c]+s,*nr=a[!c]+s+x,m=0; while(++i!=l)if(a[c][s+i]<mid)p++; for(i=-1;++i!=l;)if(a[c][s+i]<mid||a[c][s+i]==mid&&p++<x){ *nl++=a[c][s+i]; f[d][s+i]=++m; }else{ *nr++=a[c][s+i]; f[d][s+i]=m; }if(x!=1)make(!c,d+1,s,x); if(l-x!=1)make(!c,d+1,s+x,l-x);}inline getint(){ int re=0,ch=getchar(),k; while(ch!='-'&&(ch<'0'||ch>'9'))if((ch=getchar())<=0)return -1; for(k=ch=='-'&&(ch=getchar());ch>='0'&&ch<='9';ch=getchar())re=re*10+ch-48; return k?-re:re;}main(){ int i=-1,l,s,nl,nr,k,t; for(n=getint(),m=getint();++i!=n;a[0][i]=rank[i]=f[0][i]=getint()); if(n!=1){qsort(rank,n,4,cmp);make(0,0,0,n);} for(;m--;printf("%d\n",rank[s])){ nl=getint()-1;nr=getint()-1;k=getint(); for(i=s=0,l=n;l!=1;++i)if(f[i][s+nr]-(t=nl==0?0:f[i][s+nl-1])>=k){ nl=t; nr=f[i][s+nr]-1; l>>=1; }else{ k-=f[i][s+nr]-t; nl-=t; nr-=f[i][s+nr]; s+=l>>1; l-=l>>1; } }return 0;} |
有同学一定会问：ZKW线段树不是可以自底向上来避免递归嘛？那样会快很多呢！没错，但是一般线段树由孩子生成父亲的复杂度是O(1)的，而这种树则不同，而且在中位数有多个的情况下还不得不二分，又难写又慢。但是这个思路可以衍生出一个叫做“归并树”的东西。利用类似归并排序的方法构树，ASK时二分答案，在每条线段上再二分……汗……
还有一种离线的方法。如果用平衡树来维护[L,R]的KTHNUM，从[L1,R1]转为[L2,R2]的复杂度就是|L1-L2|+|R1-R2|，于是可以将询问读入后曼哈顿MST预处理，然后维护[L,R]的平衡树。这东西在区间不包含时每个数最多进一次出一次，是O(NlgN)的，常数比较小。区间包含时大约应该是O(NsqrtQlgN)的。我没写过……
如果要修改貌似就要树套树了……凌乱神马的……
【靠不上表格了】
划分树 时间复杂度O(NlgN+QlgN) 编程复杂度
归并树 时间复杂度O(NlgN+Qlg3N) 编程复杂度
曼哈顿MST+平衡树 时间复杂度O(QlgQ+NsqrtQlgN) 编程复杂度
树套树？？？？？
By Seter
2012年5月18日 08:52
莫队算法不需要用平衡树的.......直接树状数组就可以了