TIOJ 1382 約瑟問題 [segment tree]

poao899    3904K    1718MS    G++     0.80K     2009-12-07 20:09:32                                              .


線段樹越寫越簡陋=口=

是說poloo5582    3072K    1576MS    G++    0.50K     2009-11-10 22:36:00

小鬼學長超強!!


很好奇怎麼用平衡樹來寫

//*******************************

#include<stdio.h>
#define MAX 100010
struct seg{
	seg *lch,*rch;
	int l,r,rest;
	int nth(int);
}s[MAX*2];
int n,pre,now,segCnt;
seg* get(int a,int b){
	seg *p =s+segCnt++;
	p->l=a;p->r=b;p->rest=b-a+1;
	p->lch = p->rch = NULL;
	return p;
}
int seg::nth(int i){
	if(l==r){rest=0;return l;}
	int mid=(l+r)/2,rp;
	if(!lch){
		lch=get(l,mid);
		rch=get(mid+1,r);
	}
	if(lch->rest < i)
		rp=rch->nth(i - lch->rest);
	else
		rp=lch->nth(i);
	if(rp)rest--;
	return rp;
}
main(){
	while(~scanf("%d",&n)){
		//Initialize
		segCnt = 0;pre = 1;
		get(1,n);
		//Input
		for(;n;putchar(--n?32:'\n') , pre=now){
			scanf("%d",&now);
			now = (now+pre-1)%n;
			if(!now)now=n;
			printf("%d",s->nth(now));
		}
	}
}