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 , 3210 阅读

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

归并树  时间复杂度O(NlgN+Qlg3N)  编程复杂度

曼哈顿MST+平衡树  时间复杂度O(QlgQ+NsqrtQlgN)  编程复杂度

树套树?????

By Seter
  • 无匹配
MyIdea 说:
2012年5月18日 08:52

莫队算法不需要用平衡树的.......直接树状数组就可以了


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter
Host by is-Programmer.com | Power by Chito 1.3.3 beta | © 2007 LinuxGem | Design by Matthew "Agent Spork" McGee