動的ウェーブレット木

ウェーブレット木的データ構造を平衡二分探索木を使って動的にしてある。
まだ書いてる途中でたぶんバグも残ってるので注意。

#include <iostream>
#include <stdlib.h>
#include <time.h>
using namespace std;
#define uint unsigned int


class WaveletTree2{
private:
	struct node{
		uint key;  
		int l,r,p,rank;
	};

	struct node2{
		int l,r,rank;
	};

	struct recstack{
		int *p,d;
		node *m;
		node2 *m2;
	};

	int N,nptr;
	uint *wrk,skey,mkey;
	struct node *a0;
	struct node2 *b0,*b3,*stack2;
	struct recstack *pstack;

	void qs(uint *argl,uint *argr){
		if (argr-argl<16){
			for (uint t,k,*r,*l=argl+1;l<=argr;++l){
				for (k=*(r=l);argl<r && *(r-1)>k;--r) *r=*(r-1);
				*r=k;
			}
		}else{
			uint *l=argl;
			uint *r=argr;
			for (uint t,k=*(l+((r-l)>>1));l<=r;){
				while (*l<k) ++l;
				while (k<*r) --r;
				if (l<=r){
					t=*l,*l=*r,*r=t;
					++l,--r;
				}
			}
			if (argl<l-1) quick_sort(argl,l-1);
			if (l<argr) quick_sort(l,argr);
		}
	}

	int selectk(uint *p,int argr,int k){
		int l,r;
		uint u;

		while (1){
			if (argr<16){
				for (l=1;l<=argr;++l){
					u=p[l];
					for (r=l;r && p[r-1]>u;--r) p[r]=p[r-1];
					p[r]=u;
				}
				return p[k];
			}else{
				l=0;r=argr;
				u=p[r>>1];
				while (l<=r){
					while (p[l]<u) ++l;
					while (p[r]>u) --r;
					if (l<=r){
						uint t=p[l];p[l]=p[r];p[r]=t;
						++l;--r;
					}
				}
				if (k<l){
					argr=l-1;
				}else{
					p+=l;
					k-=l;
					argr-=l;
				}
			}	
		}
	}	

	inline int ll_rot(node *a, node *i0,node *i1,int ip){
		i0->rank-=i1->rank+1;
		if (i1->r) a[i1->r&INT_MAX].p=i0-a;

		i0->l=i1->r;
		i1->r=i0-a;
		i1->l&=INT_MAX;

		i0->p=i1-a;
		i1->p=ip;
		return i1-a;
	}

	inline int b_ll_rot(node2 *a,node2 *i0,node2 *i1){
		i0->rank-=i1->rank+1;

		i0->l=i1->r;
		i1->r=i0-a;
		i1->l&=INT_MAX;

		return i1-a;
	}

	inline int w_rot(node *a,node *i0,node *i1,node *i2,int ip,int lrrot){
		if (lrrot) i0->rank-=i1->rank+i2->rank+2;
		else i0->rank-=i2->rank+1;
		
		if (i2->l) a[i2->l&INT_MAX].p=i1-a;
		if (i2->r) a[i2->r&INT_MAX].p=i0-a;

		i2->rank+=i1->rank+1;

		i0->l=i2->r&INT_MAX;
		i0->r|=i2->l&INT_MIN;

		i1->l|=i2->r&INT_MIN;
		i1->r=i2->l&INT_MAX;

		i2->l=i1-a;
		i2->r=i0-a;

		i0->p=i1->p=i2-a;
		i2->p=ip;
		return i2-a;
	}

	inline int b_w_rot(node2 *a,node2 *i0,node2 *i1,node2 *i2,int lrrot){
		if (lrrot) i0->rank-=i1->rank+i2->rank+2;
		else i0->rank-=i2->rank+1;

		i2->rank+=i1->rank+1;

		i0->l=i2->r&INT_MAX;
		i0->r|=i2->l&INT_MIN;

		i1->l|=i2->r&INT_MIN;
		i1->r=i2->l&INT_MAX;

		i2->l=i1-a;
		i2->r=i0-a;

		return i2-a;
	}

	inline int rr_rot(node *a,node *i0,node *i1,int ip){
		i1->rank+=i0->rank+1;
		if (i1->l) a[i1->l&INT_MAX].p=i0-a;

		i0->r=i1->l;
		i1->l=i0-a;
		i1->r&=INT_MAX;

		i0->p=i1-a;
		i1->p=ip;
		return i1-a;
	}

	inline int b_rr_rot(node2 *a,node2 *i0,node2 *i1){
		i1->rank+=i0->rank+1;

		i0->r=i1->l;
		i1->l=i0-a;
		i1->r&=INT_MAX;

		return i1-a;
	}

	inline int le_rot(node *a,node *i0,node *i1,int ip){
		i0->rank-=i1->rank+1;
		a[i1->r].p=i0-a;
		i0->p=i1-a;

		i0->l=INT_MIN|i1->r;
		i1->r=INT_MIN|(i0-a);
		
		i1->p=ip;
		return i1-a;
	}

	inline int b_le_rot(node2 *a,node2 *i0,node2 *i1){
		i0->rank-=i1->rank+1;

		i0->l=INT_MIN|i1->r;
		i1->r=INT_MIN|(i0-a);
		
		return i1-a;
	}

	inline int re_rot(node *a,node *i0,node *i1,int ip){
		i1->rank+=i0->rank+1;
		a[i1->l].p=i0-a;
		i0->p=i1-a;

		i0->r=INT_MIN|i1->l;
		i1->l=INT_MIN|(i0-a);
		
		i1->p=ip;
		return i1-a;
	}

	inline int b_re_rot(node2 *a,node2 *i0,node2 *i1){
		i1->rank+=i0->rank+1;

		i0->r=INT_MIN|i1->l;
		i1->l=INT_MIN|(i0-a);
		
		return i1-a;
	}

	int b_lbsrc2(node2 *a,uint x,int m,int k){
		int l=0;

		for (int i=a->r;i;){
			uint u=a0[i].key>>m;
			if (u==x){
				int t=n2i(a0,i);
				if (t==k) return l+a[i].rank;
				if (k<t){
					i=a[i].l&INT_MAX;
				}else{
					l+=a[i].rank+1;
					i=a[i].r&INT_MAX;
				}
			}else if (x<u){
				i=a[i].l&INT_MAX;
			}else{
				l+=a[i].rank+1;
				i=a[i].r&INT_MAX;
			}
		}
		return l;
	}

	int b_rbsrc2(node2 *a,uint x,int m,int k,int i){
		int l=0;

		while (i){
			uint u=a0[i].key>>m;
			if (u==x){
				int t=n2i(a0,i);
				if (t==k) return l+a[i].rank;
				if (k<t){
					i=a[i].l&INT_MAX;
				}else{
					l+=a[i].rank+1;
					i=a[i].r&INT_MAX;
				}
			}else if (x<u){
				i=a[i].l&INT_MAX;
			}else{
				l+=a[i].rank+1;
				i=a[i].r&INT_MAX;
			}
		}
		return l-1;
	}

	int b_lrbsrc2(node2 *a,uint x,int m,int s,int e,int *lpos=NULL,int *rpos=NULL){
		int i,i2,t,t2,l,l2;
		i=a->r;
		l=0;

		while (i && (a0[i].key>>m)!=x){
			if (x<(a0[i].key>>m)){
				i=a[i].l&INT_MAX;
			}else{
				l+=a[i].rank+1;
				i=a[i].r&INT_MAX;
			}
		}
		if (i==0) return 0;
		
		t2=t=n2i(a0,i);
		i2=i;
		l2=l;
		
		do{
			if (s==t) {l+=a[i].rank;break;}
			if (s<t){
				i=a[i].l&INT_MAX;
			}else{
				l+=a[i].rank+1;
				i=a[i].r&INT_MAX;
			}
			while (i && (a0[i].key>>m)!=x){
				if (x<(a0[i].key>>m)){
					i=a[i].l&INT_MAX;
				}else{
					l+=a[i].rank+1;
					i=a[i].r&INT_MAX;
				}
			}
			if (!i) break;
			t=n2i(a0,i);
		}while (1);
				
		do{
			if (e==t2) {l2+=a[i2].rank+1;break;}
			if (e<t2){
				i2=a[i2].l&INT_MAX;
			}else{
				l2+=a[i2].rank+1;
				i2=a[i2].r&INT_MAX;
			}
			while (i2 && (a0[i2].key>>m)!=x){
				if (x<(a0[i2].key>>m)){
					i2=a[i2].l&INT_MAX;
				}else{
					l2+=a[i2].rank+1;
					i2=a[i2].r&INT_MAX;
				}
			}
			if (!i2) break;
			t2=n2i(a0,i2);
		}while (1);

		if (lpos!=NULL){
			*lpos=l;
			*rpos=l2-1;
		}
		return l2-l;
	}

	int b_lbsrc_p0(node2 *a,uint x,int i){
		int l=0;
		while (i){
			if (x<=a0[i].key){
				i=a[i].l&INT_MAX;
			}else{
				l+=a[i].rank+1;
				i=a[i].r&INT_MAX;
			}
		}
		return l;
	}

	void get_sequence(node2 *a,int s,int e,int argr,uint *w,node2 *st){
		int i,k,l,r;
		node2 *sp=st+1;

		i=st->rank=a->r;st->l=0;st->r=argr;
		while (st<sp){
			--sp;
			i=sp->rank;
			l=sp->l;r=sp->r;
			k=l+a[i].rank;
			if (s<=k && k<=e) *w++=i;
			if (l<=e && s<=r){
				if (a[i].r){
					sp->rank=a[i].r&INT_MAX;
					sp->l=k+1;sp->r=r;
					++sp;
				}
				if (a[i].l){
					sp->rank=a[i].l&INT_MAX;
					sp->l=l;sp->r=k-1;
					++sp;
				}
			}
		}
	}

	inline int n2i(node *a,int i){
		int k=a[i].rank;
		for (int c=i;i=a[i].p;c=i){
			if ((a[i].r&INT_MAX)==c) k+=a[i].rank+1;
		}
		return k;
	}

	int get_ca(node2 *a,uint x,int m){
		int i=a->r;
		while (i && (a0[i].key>>m)!=x){
			if (x<(a0[i].key>>m)) i=a[i].l&INT_MAX;
			else i=a[i].r&INT_MAX;
		}
		return i;
	}

	int get_ca(node2 *a,uint x){
		int i=a->r;
		while (i && a0[i].key!=x){
			if (x<a0[i].key) i=a[i].l&INT_MAX;
			else i=a[i].r&INT_MAX;
		}
		return i;
	}

	inline uint getseq_selectk(node2 *p,int l,int r,int k,uint *w){
		get_sequence(p,l,r,nptr-1,w,stack2);
		for (uint *q=w+r-l;w<=q;--q) *q=a0[*q].key;
		return selectk(w,r-l,k)&mkey;
	}

	uint nxt(node2 *a,uint x,int m){
		if ((x&255)==255) return 256;
		uint u,v=256;
		for (int i=a->r;i;){
			u=a0[i].key>>m;
			if (x<u){
				v=u;
				i=a[i].l&INT_MAX;
			}else{
				i=a[i].r&INT_MAX;
			}
		}
		return v&255;
	}

	uint pre(node2 *a,uint x,int m){
		if ((x&255)==0) return 256;
		uint u,v=256;
		for (int i=a->r;i;){
			u=a0[i].key>>m;
			if (x<=u){
				i=a[i].l&INT_MAX;
			}else{
				v=u;
				i=a[i].r&INT_MAX;
			}
		}
		return v&255;
	}

	uint quantile_d(int s,int e,int k){
		int l,r,t;
		uint u=0;
		node2 *p=b0;

		for (int i=24;0<=i;i-=8,p+=N){
			for (uint v=255;v<256;k-=t){
				t=b_lrbsrc2(p,(u>>i)|v,i,s,e,&l,&r);
				if (t>k){
					u|=v<<i;
					break;
				}
				v=pre(p,(u>>i)|v,i);
			}
			if (i && t<1024) return getseq_selectk(p,l,r,r-l-k,wrk);
		}
		return u&mkey;
	}

	void insert2(node *a,uint key,int k){
		recstack *ps=pstack;
		ps->p=&a->r;

		for (ps->m=a+a->r;ps->m!=a;++ps){
			if (k<=ps->m->rank){
				ps[1].m=a+(*(ps[1].p=&ps->m->l)&INT_MAX);
				ps->m->rank++;
				ps->d=0;
			}else{
				ps[1].m=a+(*(ps[1].p=&ps->m->r)&INT_MAX);
				k-=ps->m->rank+1;
				ps->d=1;
			}
		}

		if (a->p){
			int t=a->p;
			a->p=(ps->m=a+(*ps->p=t))->l;
		}else{
			ps->m=a+(*ps->p=++(a->rank));
		}
		ps->m->key=key;
		ps->m->l=ps->m->r=ps->m->rank=0;
		ps->m->p= pstack<ps ? ps[-1].m-a: 0;
		*ps->p=ps->m-a;

		for (int ch=ps->m-a;pstack<=--ps;ch=ps->m-a){
			if (ps->m->l&INT_MIN){
				if (ps->d) ps->m->l&=INT_MAX;
				else if (a[ch].l&INT_MIN) *ps->p=(*ps->p&INT_MIN)+ll_rot(a,ps->m,a+ch,ps->m->p);
				else *ps->p=(*ps->p&INT_MIN)+w_rot(a,ps->m,a+ch,a+(a[ch].r&INT_MAX),ps->m->p,1);
				break;
			}else if (ps->m->r&INT_MIN){
				if (!ps->d) ps->m->r&=INT_MAX;
				else if (a[ch].r&INT_MIN) *ps->p=(*ps->p&INT_MIN)+rr_rot(a,ps->m,a+ch,ps->m->p);
				else *ps->p=(*ps->p&INT_MIN)+w_rot(a,a+ch,ps->m,a+(a[ch].l&INT_MAX),ps->m->p,0);
				break;
			}else if (ps->d){
					ps->m->r|=INT_MIN;
			}else{
					ps->m->l|=INT_MIN;
			}
		}
	}

	void b_insert2(node2 *a,int k){
		recstack *ps=pstack;
		ps->p=&a->r;

		for (ps->m2=a+a->r;ps->m2!=a;++ps){
			if (k<=ps->m2->rank){
				ps[1].m2=a+(*(ps[1].p=&ps->m2->l)&INT_MAX);
				ps->m2->rank++;
				ps->d=0;
			}else{
				ps[1].m2=a+(*(ps[1].p=&ps->m2->r)&INT_MAX);
				k-=ps->m2->rank+1;
				ps->d=1;
			}
		}

		if (a->l){
			int t=a->l;
			a->l=(ps->m2=a+(*ps->p=t))->l;
		}else{
			ps->m2=a+(*ps->p=++(a->rank));
		}
		ps->m2->l=ps->m2->r=ps->m2->rank=0;
		*ps->p=ps->m2-a;

		for (int ch=ps->m2-a;pstack<=--ps;ch=ps->m2-a){
			if (ps->m2->l&INT_MIN){
				if (ps->d) ps->m2->l&=INT_MAX;
				else if (a[ch].l&INT_MIN) *ps->p=(*ps->p&INT_MIN)+b_ll_rot(a,ps->m2,a+ch);
				else *ps->p=(*ps->p&INT_MIN)+b_w_rot(a,ps->m2,a+ch,a+(a[ch].r&INT_MAX),1);
				break;
			}else if (ps->m2->r&INT_MIN){
				if (!ps->d) ps->m2->r&=INT_MAX;
				else if (a[ch].r&INT_MIN) *ps->p=(*ps->p&INT_MIN)+b_rr_rot(a,ps->m2,a+ch);
				else *ps->p=(*ps->p&INT_MIN)+b_w_rot(a,a+ch,ps->m2,a+(a[ch].l&INT_MAX),0);
				break;
			}else if (ps->d){
					ps->m2->r|=INT_MIN;
			}else{
					ps->m2->l|=INT_MIN;
			}
		}
	}

	void  remove2(node *a,int k){
		recstack *rempos,*ps=pstack;

		ps->p=&a->r;
		for (ps->m=a+a->r;ps->m->rank!=k;ps->m=a+(*ps->p&INT_MAX)){
			if (k<ps->m->rank){
				ps[1].p=&ps->m->l;
				ps->m->rank--;
				ps->d=0;
			}else{
				ps[1].p=&ps->m->r;
				k-=ps->m->rank+1;
				ps->d=1;
			}
			++ps;
		}

		if (ps->m->l){
			if (ps->m->r){
				rempos=ps;
				ps->d=0;
				ps->m->rank--;
				++ps;
				for (ps->m=a+(*(ps->p=&ps[-1].m->l)&INT_MAX);ps->m->r;++ps){
					ps->d=1;
					ps[1].m=a+(*(ps[1].p=&ps->m->r)&INT_MAX);
				}

				*ps->p=(*ps->p&INT_MIN)+(ps->m->l&INT_MAX);
				if (ps->m->l) a[ps->m->l&INT_MAX].p=ps->m->p;

				ps->m->l=rempos->m->l;
				ps->m->r=rempos->m->r;
				ps->m->p=rempos->m->p;
				ps->m->rank=rempos->m->rank;
				*rempos->p=(*rempos->p&INT_MIN)+(ps->m-a);

				if (ps->m->l){
					a[ps->m->l&INT_MAX].p=ps->m-a;
				}
				a[ps->m->r&INT_MAX].p=ps->m-a;
				rempos->m->l=a->p; a->p=rempos->m-a;
				rempos->m=ps->m;
				(rempos+1)->p=&ps->m->l;
			}else{
				*ps->p=(*ps->p&INT_MIN)+(ps->m->l&INT_MAX);
				a[ps->m->l&INT_MAX].p=ps->m->p;
				ps->m->l=a->p; a->p=ps->m-a;				
			}
		}else if (ps->m->r){
			*ps->p=(*ps->p&INT_MIN)+(ps->m->r&INT_MAX);
			a[ps->m->r&INT_MAX].p=ps->m->p;
			ps->m->l=a->p; a->p=ps->m-a;
		}else{
			*ps->p&=INT_MIN;
			ps->m->l=a->p; a->p=ps->m-a;
		}

		while (pstack<=--ps){
			if (ps->m->l&INT_MIN){
				if (ps->d){
					node *m=a+(ps->m->l&INT_MAX);
					if (m->l&INT_MIN){
						*ps->p=(*ps->p&INT_MIN)+ll_rot(a,ps->m,m,ps->m->p);
					}else if (m->r&INT_MIN){
						*ps->p=(*ps->p&INT_MIN)+w_rot(a,ps->m,m,a+((m->r)&INT_MAX),ps->m->p,1);
					}else{ 
						*ps->p=(*ps->p&INT_MIN)+le_rot(a,ps->m,m,ps->m->p);
						break;
					}
				}else{
					ps->m->l&=INT_MAX;
				}
			}else if (ps->m->r&INT_MIN){
				if (!ps->d){
					node *m=a+(ps->m->r&INT_MAX);
					if (m->l&INT_MIN){
						*ps->p=(*ps->p&INT_MIN)+w_rot(a,m,ps->m,a+((m->l)&INT_MAX),ps->m->p,0);
					}else if (m->r&INT_MIN){
						*ps->p=(*ps->p&INT_MIN)+rr_rot(a,ps->m,m,ps->m->p);
					}else{ 
						*ps->p=(*ps->p&INT_MIN)+re_rot(a,ps->m,m,ps->m->p);
						break;
					}
				}else{
					ps->m->r&=INT_MAX;
				}
			}else{
				//*((&ps->m->r)-(ps->d))|=INT_MIN;return;
				if (ps->d) ps->m->l|=INT_MIN;
				else ps->m->r|=INT_MIN;
				break;
			}
		}
	}

	void  b_remove2(node2 *a,int k){
		recstack *rempos,*ps=pstack;

		ps->p=&a->r;
		for (ps->m2=a+a->r;ps->m2->rank!=k;ps->m2=a+(*ps->p&INT_MAX)){
			if (k<ps->m2->rank){
				ps[1].p=&ps->m2->l;
				ps->m2->rank--;
				ps->d=0;
			}else{
				ps[1].p=&ps->m2->r;
				k-=ps->m2->rank+1;
				ps->d=1;
			}
			++ps;
		}

		if (ps->m2->l){
			if (ps->m2->r){
				rempos=ps;
				ps->d=0;
				ps->m2->rank--;
				++ps;
				for (ps->m2=a+(*(ps->p=&ps[-1].m2->l)&INT_MAX);ps->m2->r;++ps){
					ps->d=1;
					ps[1].m2=a+(*(ps[1].p=&ps->m2->r)&INT_MAX);
				}

				*ps->p=(*ps->p&INT_MIN)+(ps->m2->l&INT_MAX);
				ps->m2->l=rempos->m2->l;
				ps->m2->r=rempos->m2->r;
				ps->m2->rank=rempos->m2->rank;
				*rempos->p=(*rempos->p&INT_MIN)+(ps->m2-a);
				rempos->m2->l=a->l;a->l=rempos->m2-a;
				rempos->m2=ps->m2;
				(rempos+1)->p=&ps->m2->l;
			}else{
				*ps->p=(*ps->p&INT_MIN)+(ps->m2->l&INT_MAX);
				ps->m2->l=a->l;a->l=ps->m2-a;
			}
		}else if (ps->m2->r){
			*ps->p=(*ps->p&INT_MIN)+(ps->m2->r&INT_MAX);
			ps->m2->l=a->l; a->l=ps->m2-a;
		}else{
			*ps->p&=INT_MIN;
			ps->m2->l=a->l; a->l=ps->m2-a;
		}

		while (pstack<=--ps){
			if (ps->m2->l&INT_MIN){
				if (ps->d){
					node2 *m=a+(ps->m2->l&INT_MAX);
					if (m->l&INT_MIN){
						*ps->p=(*ps->p&INT_MIN)+b_ll_rot(a,ps->m2,m);
					}else if (m->r&INT_MIN){
						*ps->p=(*ps->p&INT_MIN)+b_w_rot(a,ps->m2,m,a+((m->r)&INT_MAX),1);
					}else{ 
						*ps->p=(*ps->p&INT_MIN)+b_le_rot(a,ps->m2,m);
						break;
					}
				}else{
					ps->m2->l&=INT_MAX;
				}
			}else if (ps->m2->r&INT_MIN){
				if (!ps->d){
					node2 *m=a+(ps->m2->r&INT_MAX);
					if (m->l&INT_MIN){
						*ps->p=(*ps->p&INT_MIN)+b_w_rot(a,m,ps->m2,a+((m->l)&INT_MAX),0);
					}else if (m->r&INT_MIN){
						*ps->p=(*ps->p&INT_MIN)+b_rr_rot(a,ps->m2,m);
					}else{ 
						*ps->p=(*ps->p&INT_MIN)+b_re_rot(a,ps->m2,m);
						break;
					}
				}else{
					ps->m2->r&=INT_MAX;
				}
			}else{
				if (ps->d) ps->m2->l|=INT_MIN;
				else ps->m2->r|=INT_MIN;
				break;
			}
		}
	}

	inline uint search(node *a,int k){
		node *m=a+a->r;

		while (m->rank!=k){
			if (k<m->rank){
				m=a+(m->l&INT_MAX);
			}else{
				k-=m->rank+1;
				m=a+(m->r&INT_MAX);
			}
		}
		return m->key;
	}

	inline int b_search(node2 *a,int k){
		int i=a->r;

		while (a[i].rank!=k){
			if (k<a[i].rank){
				i=a[i].l&INT_MAX;
			}else{
				k-=a[i].rank+1;
				i=a[i].r&INT_MAX;
			}
		}
		return i;
	}

	int init2_a_h(int i,int l,int r,int ip,int *h){
		int t0,t1,h0,h1;

		if (l<i){
			t0=(l+i-1)>>1;
			a0[i].l=t0;
			t0=init2_a_h(t0,l,i-1,i,&h0);
		}else{
			t0=a0[i].l=0;
			h0=-1;
		}
		
		if (i<r){
			t1=(i+1+r)>>1;
			a0[i].r=t1;
			t1=init2_a_h(t1,i+1,r,i,&h1);
		}else{
			t1=a0[i].r=0;
			h1=-1;
		}

		a0[i].p=ip;
		a0[i].rank=t0;
		if (h0<h1){
			a0[i].r|=INT_MIN;
			*h=h1+1;
		}else if (h0>h1){
			a0[i].l|=INT_MIN;
			*h=h0+1;
		}else{
			*h=h0+1;
		}
		return t0+t1+1;
	}

	void init2_b1b2(node2 *b,int i,int l,int r,int j,int *h,int *rank){
		int h0,h1,rnk0,rnk1;
		
		if (l<i){
			int t=(l+i-1)>>1;
			b[j].l=a0[t].rank;
			init2_b1b2(b,t,l,i-1,b[j].l,&h0,&rnk0);
		}else{
			b[j].l=0;
			h0=-1;rnk0=0;
		}

		if (i<r){
			int t=(i+1+r)>>1;
			b[j].r=a0[t].rank;
			init2_b1b2(b,t,i+1,r,b[j].r,&h1,&rnk1);
		}else{
			b[j].r=0;
			h1=-1;rnk1=0;
		}
		
		b[j].rank=rnk0;
		*rank=rnk0+rnk1+1;

		if (h0<h1){
			b[j].r|=INT_MIN;
			*h=h1+1;
		}else if (h0>h1){
			b[j].l|=INT_MIN;
			*h=h0+1;
		}else{
			*h=h0+1;
		}
	}

	void init2_b(node2 *a,int n,int s,uint *c){
		int i,j,t;
		uint u;

		if (n<32){
			for (i=1;i<n;++i){
				t=a[i].l;
				u=(a0[t].key>>s)&255;
				for (j=i;0<j;--j){
					if (((a0[a[j-1].l].key>>s)&255)<=u) break;
					a[j].l=a[j-1].l;
				}
				a[j].l=t;
			}
			for (i=0;i<n;++i) a[i].rank=a[i].l;

			if (s){
				node2 *p=a+N;
				for (i=0;i<n;++i) p[i].rank=p[i].l=a[i].l;
			
				for (i=0;i<n;i=j){
					u=(a0[a[i].l].key>>s)&255;
					for (j=i+1;j<n;++j){
						if (((a0[a[j].l].key>>s)&255)!=u) break;
					}
					init2_b(p+i,j-i,s-8,c+258);
				}
			}
		}else{

			for (i=0;i<=256;++i) c[i]=0;
			for (i=0;i<n;++i) ++c[a[i].r=((a0[a[i].l].key)>>s)&255];
			for (i=1;i<=256;++i) c[i]+=c[i-1];
			for (i=n-1;0<=i;--i) a[--c[a[i].r]].rank=a[i].l;

			if (s){
				node2 *p=a+N;
				for (i=0;i<n;++i) p[i].l=a[i].rank;
				for (i=0;i<256;++i){
					if (c[i]<c[i+1]){
						init2_b(p+c[i],c[i+1]-c[i],s-8,c+258);
					}
				}
			}
		}
	}


public:
	
	// n:最大入力件数 v:最大入力値
	WaveletTree2(int n, uint v=4294967295){
		N=n+1;
		a0=new struct node[N];
		b0=new struct node2[N*4+50];
		pstack=new struct recstack[50];
		wrk=new uint[258+1026];
		b3=b0+N*3;
		stack2=b3+N;

		a0->key=a0->l=a0->p=a0->r=a0->rank=0;
		for (node2 *p=b0;p<stack2;p+=N) p->l=p->r=p->rank=0;
		
		for (skey=0;(v<<skey)<0x80000000;++skey);
		mkey=UINT_MAX>>skey;
		nptr=0;
	}
	~WaveletTree2(){ 
		delete [] a0,delete [] pstack,delete [] wrk,delete [] b0;
	}

	
	// [0,i]における値xの出現回数
	int rank(int i,uint x){
		x+=(x<<skey)&~mkey;
		int j=get_ca(b3,x);
		return b_rbsrc2(b3,x,0,i,j)+1-b_lbsrc_p0(b3,x,j);
	}


	// [s,e]におけるrank
	int rangerank(int s,int e,uint x){
		return b_lrbsrc2(b3,x+((x<<skey)&~mkey),0,s,e);
	}


	// i番目に値xが出現する位置(存在しない場合は-1を返す)
	int select(int i,uint x){
		x+=(x<<skey)&~mkey;
		int l=b_lbsrc_p0(b3,x,b3->r);
		if ((l+i>=nptr) || (a0[l=b_search(b3,l+i)].key!=x)) return -1;
		return n2i(a0,l);
	}


	// s番目の位置を先頭としたときのselect
	int rangeselect(int s,int i,uint x){
		x+=(x<<skey)&~mkey;
		int l=b_lbsrc2(b3,x,0,s);
		if ((l+i>=nptr) || (a0[l=b_search(b3,l+i)].key!=x)) return -1;
		return n2i(a0,l);
	}


	// [s,e]をソートしたときのk番目に位置する値
	uint quantile(int s,int e,int k){
		if (k>((e-s)>>1)) return quantile_d(s,e,e-s-k);
		int l,r,t;
		uint u=0;
		node2 *p=b0;

		for (int i=24;0<=i;i-=8,p+=N){
			for (uint v=0;v<256;k-=t){
				t=b_lrbsrc2(p,(u>>i)|v,i,s,e,&l,&r);
				if (t>k){
					u|=v<<i;
					break;
				}
				v=nxt(p,(u>>i)|v,i);
			}
			if (i && t<1024) return getseq_selectk(p,l,r,k,wrk);
		}
		return u&mkey;
	}


	// [s,e]をソートしたときの小さいほうからk+1個をans配列に返す
	void rangemink(int s,int e,int k,uint *ans){
		int l,r,t,k2=k;
		uint u=0;
		node2 *p=b0;
		uint *q=ans;

		for (int i=24;0<=i;i-=8,p+=N){
			for (uint v=0;v<256;++v,k-=t){
				t=b_lrbsrc2(p,(u>>i)|v,i,s,e,&l,&r);
				if (t>k){
					if (i){
						u|=v<<i;
					}else{
						for (u=(u|v)&mkey;0<=k;--k) *q++=u;
					}
					break;
				}else if (t){
					get_sequence(p,l,r,nptr-1,q,stack2);
					for (int j=t;j--;++q) *q=a0[*q].key&mkey;
				}
			}
			if (i && t<1024){
				get_sequence(p,l,r,nptr-1,wrk,stack2);
				for (int j=0;j<t;++j) wrk[j]=a0[wrk[j]].key&mkey;
				qs(wrk,wrk+t-1);
				for (int j=0;j<=k;++j) *q++=wrk[j];
				break;
			}
		}
		qs(ans,ans+k2);
	}

	// [s,e]をソートしたときの大きいほうからk+1個をans配列に返す
	void rangemaxk(int s,int e,int k,uint *ans){
		int l,r,t,k2=k;
		uint u=0;
		node2 *p=b0;
		uint *q=ans;

		for (int i=24;0<=i;i-=8,p+=N){
			for (uint v=256;v--;k-=t){
				t=b_lrbsrc2(p,(u>>i)|v,i,s,e,&l,&r);
				if (t>k){
					if (i){
						u|=v<<i;
					}else{
						for (u=(u|v)&mkey;0<=k;--k) *q++=u;
					}
					break;
				}else if (t){
					get_sequence(p,l,r,nptr-1,q,stack2);
					for (int j=t;j--;++q){
						*q=a0[*q].key&mkey;
					}
				}
			}
			if (i && t<1024){
				get_sequence(p,l,r,nptr-1,wrk,stack2);
				for (int j=0;j<t;++j) wrk[j]=a0[wrk[j]].key&mkey;
				qs(wrk,wrk+t-1);
				for (;0<=k;--k) *q++=wrk[--t];
				break;
			}
		}
		qs(ans,ans+k2);
		for (l=0,r=k2;l<r;++l,--r){
			u=ans[l];ans[l]=ans[r];ans[r]=u;
		}
	}

	// 値xをk番目の位置に追加
	void insert(uint x,int k){
		node2 *p=b0;
		x+=(x<<skey)&~mkey;

		for (int i=24;0<=i;i-=8,p+=N){
			b_insert2(p,b_lbsrc2(p,x>>i,i,k));
		}
		insert2(a0,x,k);
		++nptr;
	}

	// k番目に位置する値を削除
	uint remove(int k){
		node2 *p=b0;
		uint v=search(a0,k);

		for (int i=24;0<=i;i-=8,p+=N){
			b_remove2(p,b_lbsrc2(p,v>>i,i,k));
		}
		remove2(a0,k);
		--nptr;
		return v&mkey;
	}

	// k番目に位置する値を返す
	uint access(int k){
		int i=a0->r;
		while (a0[i].rank!=k){
			if (k<a0[i].rank){
				i=a0[i].l&INT_MAX;
			}else{
				k-=a0[i].rank+1;
				i=a0[i].r&INT_MAX;
			}
		}
		return a0[i].key&mkey;
	}


	// 初期化用のinsert
	void init(uint x,int i){
		a0[i+1].key=x+((x<<skey)&~mkey);
		++nptr;
	}


	// init後にこれを実行すると初期化完了
	void init2(){
		node2 *p=b0;
		int i,j,x,m=a0->r=(1+nptr)>>1;

		for (i=1;i<=nptr;++i) b0[i].l=i;
		init2_b(b0+1,nptr,24,wrk);
		
		for (j=4;j--;p+=N){
			p->r=p[m].rank;
			for (i=1;i<=nptr;++i) a0[i].rank=p[i].rank;
			init2_b1b2(p,m,1,nptr,p->r,&x,&x);
			p->rank=nptr;
		}
	
		init2_a_h(m,1,nptr,0,&x);
		a0->rank=nptr;
	}
};



int main(void){
	int i,n,t;
	uint u,x,*c;

	// 最大入力件数
	n=100000;

	// 最大入力値
	const uint v=1000000000;

	WaveletTree2 wt(n,v);


	// m種類の入力値
	const int m=1000;
	c=new uint[m];
	for (i=0;i<m;++i) c[i]=(double)rand() / (RAND_MAX + 1) * v;


	// 初期化
	for (i=0;i<n;++i){
		t=(double)rand() / (RAND_MAX + 1) * m;
		x=c[t];
		wt.init(x,i);
	}
	wt.init2();

	wt.remove(10);
	wt.insert(x,10);
	u=wt.access(10);
	u=wt.quantile(10,100,10);
	t=wt.rank(1000,x);
	t=wt.select(10,x);
	t=wt.rangerank(10,1000,x);
	t=wt.rangeselect(1000,0,x);

	uint ans[10];
	wt.rangemink(10,1000,9,ans);
	//wt.rangemaxk(10,1000,9,ans);
	for (i=0;i<10;++i) cout<<ans[i]<<endl;

	delete [] c;
	return 0;
}