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