1901: Zju2112 Dynamic Rankings - #include <Seter> - using namespace Orz;

1901: Zju2112 Dynamic Rankings

Seter posted @ 2012年2月01日 13:16 in BZOJ with tags ChairTree SegTree , 20839 阅读

http://www.zybbs.org/JudgeOnline/problem.php?id=1901

RunID User Problem Result Memory Time Language Code Length Submit Time
197772 Seter 1901 Accepted 31456 kb 380 ms C/Edit 2168 B 2012-02-01 11:05:39

贾教364ms……像个BUG一样……开挂呢罢……我就差重写qsort了……刷不动啊!

首先果断ymFotile……主席树(ChairTree)实在是太神了……

主席树大概是一种离线结构,我以前反正没看到过这东西,所以就自己给他起名字了!如果谁知道这东西的真名,请告诉我!

主席树的主体是线段树,准确的说,是很多棵线段树,存的是一段数字区间出现次数(所以要先离散化可能出现的数字)。

举个例子,假设我每次都要求整个序列内的第k小,那么对整个序列构造一个线段树,然后在线段树上不断找第k小在当前数字区间的左半部分还是右半部分。这个操作和平衡树的Rank操作一样,只是这里将离散的数字搞成了连续的数字。


先假设没有修改操作:

对于每个前缀S1...i,保存这样一个线段树Ti,组成主席树。这样不是会MLE么?最后再讲。

注意,这个线段树对一条线段,保存的是这个数字区间的出现次数,所以是可以互相加减的!还有,由于每棵线段树都要保存同样的数字,所以它们的大小、形态也都是一样的!这实在是两个非常好的性质,是平衡树所不具备的。

对于询问(i,j),我只要拿出Tj和Ti-1,对每个节点相减就可以了。说的通俗一点,询问i...j区间中,一个数字区间的出现次数时,就是这些数字在Tj中出现的次数减去在 Ti-1中出现的次数。

那么有修改操作怎么办呢?

如果将询问看成求一段序列的数字和,那么上面那个相当于求出了前缀和。加入修改操作后,就要用树状数组等来维护前缀和了。于是那个“很好的性质”又一次发挥了作用,由于主席树可以互相加减,所以可以用树状数组来套上它。做法和维护前缀和长得基本一样,不说了。


开始填坑。由于每棵线段树的大小形态都是一样的,而且初始值全都是0,那每个线段树都初始化不是太浪费了?所以一开始只要建一棵空树即可。

然后是在某棵树上修改一个数字,由于和其他树相关联,所以不能在原来的树上改,必须弄个新的出来。难道要弄一棵新树?不是的,由于一个数字的更改只影响了一条从这个叶子节点到根的路径,所以只要只有这条路径是新的,另外都没有改变。比如对于某个节点,要往右边走,那么左边那些就不用新建,只要用个指针链到原树的此节点左边就可以了,这个步骤的前提也是线段树的形态一样。

假设s是数字个数,这个步骤的空间复杂度显然是O(logs)。用树状数组去套它,共有2logn棵树被修改,m个操作再加上一开始的空树和n个数字,总共就是O((n+m)lognlogs)。Fotile大神说如果加上垃圾回收的话,可以去掉一个log……ym

 

#include <stdio.h>
#include <stdlib.h>
#define S struct Seg
#define mid (l+r>>1)
char*sp,str[1000000],*p=str;
int n,m,a[20001][2],s,ra[20001],K,Y=1,I,b[20000],v[10001]={-2,-2};
S{S*c[2];int s}*R[10001],st[2500000],*stp=st,*T[10001];
getint(){
	int re=0;
	while(*p<'0'||*p>'9')p++;
	while(*p>='0'&&*p<='9')re=re*10+*p++-48;
	return re;
}cmp(const void*a,const void*b){return*(int*)b-*(int*)a;}
S*Build(l,r){
	S*node=stp++;
	if(l+1!=r)node->c[0]=Build(l,mid),node->c[1]=Build(mid,r);
	return node;
}S*SegInsert(x,l,r)S*x;int l,r;{
	S*node=stp++;node->s=x->s+Y;
	if(l+1!=r){
		if(I<mid)node->c[1]=x->c[1],node->c[0]=SegInsert(x->c[0],l,mid);
		else node->c[0]=x->c[0],node->c[1]=SegInsert(x->c[1],mid,r);
	}return node;
}void BitInsert(x){for(;x<=n;x+=x&-x)R[x]=SegInsert(R[x],0,K);}
void Init(x){for(;x;x-=x&-x)if(v[x]!=m)v[x]=m,T[x]=R[x];else v[x]=-2;}
void Turn(int x,_Bool c){for(;x;x-=x&-x)if(v[x]==m)T[x]=T[x]->c[c];}
BitQuery(x){int ans=0;for(;x;x-=x&-x)if(v[x]==m)ans+=T[x]->c[0]->s;return ans;}
void print(x){
	char out[10],*buf=out;
	if(!x)*sp++='0';
	else{
		while(x)*buf++=x%10+48,x/=10;
		while(buf--!=out)*sp++=*buf;
	}*sp++='\n';
}main(){
	int i,j,k,re,l,r;fread(p,1,1000000,stdin);
	for(s=n=i=getint(),m=getint();i--;a[i][1]=n-i-1)a[i][0]=getint();
	for(sp=p;*p;)if(*p++=='C')getint(),a[s][1]=s,a[s++][0]=getint();
	a[a[s][1]=s][0]=ra[s]=-1;
	for(qsort(a,s,8,cmp);s--;b[ra[a[s][1]]=ra[a[s+1][1]]+(a[s][0]!=a[s+1][0])]=a[s][0]);
	for(R[i=1]=Build(0,K=ra[a[0][1]]+1);i++!=n;v[i]=-2)R[i]=R[1];
	for(s=n,p=sp,sp=str,i=-1;++i!=n;BitInsert(i+1))I=ra[i];
	while(m--){
		while(*p!='Q'&&*p!='C')p++;
		if(*p=='Q'){
			i=getint()-1;j=getint();k=getint();
			Init(i);Init(j);l=0;r=K;
			while(l+1!=r)if((re=BitQuery(j)-BitQuery(i))>=k)Turn(i,0),Turn(j,0),r=mid;
			else Turn(i,1),Turn(j,1),k-=re,l=mid;
			print(b[l]);
		}else if(ra[(i=getint())-1]!=ra[s++]){
			I=ra[i-1];Y=-1;BitInsert(i);
			I=ra[i-1]=ra[s-1];Y=1;BitInsert(i);
		}
	}fwrite(str,1,sp-str,stdout);return 0;
}
By Seter
  • 无匹配
roosephu 说:
2012年2月21日 15:15

感觉这个就是函数式编程的线段树……

roosephu 说:
2012年3月01日 22:19

大神用什么编译器呀?为啥我总觉得这代码gcc系列不会通过呢?

Avatar_small
Seter 说:
2012年3月02日 18:52

反正各种OJ上都能过。。。

nkuflk 说:
2012年7月24日 17:12

YM大神,这么神的东西。。就是排版看着真费劲。。


登录 *


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