3946. K-th Number - #include <Seter> - using namespace Orz;

3946. K-th Number

Seter posted @ 2011年10月07日 10:49 in SPOJ with tags SegTree PartTree Classical , 3308 阅读

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组数据就说明对了：

#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) 编程复杂度