一道很有意思的神题~

暴力平衡树的复杂度很对（并不），但是$2^{30}$的空间一脸屎

这题的正解是一个类似线段树的数据结构，我觉得很有创新性Orz

首先可以想到一种暴力就是用一个点代表一个区间，然后用链表维护这些点的集合，每次alloc操作就相当于割开未分配的区间，即增加了一个点，free操作就相当于合并。所以最多会产生$n$个点，单次操作$O(n)$，时间复杂度$O(n^2)$但是不满，貌似常数小就可以拿60；

把这个集合看成一个序列的话，快速修改点的信息肯定会想到线段树，正解就是用线段树去维护这个“区间集合”；

但是直接暴力线段树的话并不比平衡树优，需要用类似区间修改打懒标记的方法：如果一个点没被分割过，那就先打上标记，不实际创建它的儿子，到访问时才真正建出来，这样就能达到每次操作均摊$O(logn)$的复杂度。

开始算了算$2^{30}$线段树需要一千多万个节点，觉得很虚，结果一看空间1G瞬间不虚。。。

其实我一直很喜欢这种二叉结构，觉得很优美，写起来也很舒服。。。

代码：

 #include<algorithm>

 #include<iostream>

 #include<cstring>

 #include<cstdio>

 #include<cmath>

 #include<queue>

 #define inf 2147483647

 #define eps 1e-9

 #define DCSB {puts("failed");continue;}

 using namespace std;

 typedef long long ll;

 struct node{

     int lc,rc,v,bit;

 }t[];

 int T,n,op,p,q,rt,cnt,tot,rts[];

 void pd(int u){

     if(t[u].bit==-)return;

     if(t[u].bit>){

         t[u].lc=++cnt;

         t[u].rc=++cnt;

         t[t[u].lc].bit=t[t[u].rc].bit=t[u].bit-;

         t[t[u].lc].v=t[t[u].rc].v=<<(t[u].bit-);

     }else t[u].lc=t[u].rc=-;

     t[u].bit=-;

 }

 int ins(int u,int p){

     int now=++cnt,ret=now;

     pd(u);

     while(t[u].lc!=-){

         t[now].bit=-;

         t[u].v-=p;

         t[now].v=p;

         if(p<t[t[u].lc].v){

             t[now].rc=;

             now=t[now].lc=++cnt;

             u=t[u].lc;

         }else{

             p-=t[t[u].lc].v;

             t[now].lc=t[u].lc;

             t[now].rc=++cnt;

             t[u].lc=;

             now=t[now].rc;

             u=t[u].rc;

         }

         pd(u);

     }

     t[u].v-=p;

     t[now].bit=-;

     t[now].v=p;

     t[now].lc=-;

     return ret;

 }

 int del(int u,int v){

     if(!u||!v)return u|v;

     if(t[u].lc!=-){

         t[u].lc=del(t[u].lc,t[v].lc);

         t[u].rc=del(t[u].rc,t[v].rc);

     }

     t[u].v+=t[v].v;

     return u;

 }

 int calc(int u,int p){

     int ret=;

     while(t[u].bit==-&&t[u].lc!=-){

         ret*=;

         if(t[u].lc&&p<t[t[u].lc].v)u=t[u].lc;

         else{

             p-=t[t[u].lc].v;

             u=t[u].rc;

             ret++;

         }

     }

     if(t[u].bit==-)return ret;

     else return ret*(<<t[u].bit)+p;

 }

 int main(){

     scanf("%d",&T);

     while(T--){

         rt=cnt=;

         t[].bit=;

         t[].v=<<;

         tot=;

         scanf("%d",&n);

         for(int i=;i<=n;i++){

             scanf("%d",&op);

             if(op==){

                 scanf("%d",&p);

                 rts[++tot]=;

                 if(t[rt].v<p)DCSB

                 rts[tot]=ins(rt,p);

                 puts("ok");

             }

             if(op==){

                 scanf("%d",&p);

                 if(p>tot||!rts[p])DCSB

                 rt=del(rt,rts[p]);

                 rts[p]=;

                 puts("ok");

             }

             if(op==){

                 scanf("%d%d",&p,&q);

                 if(p>tot||!rts[p]||q>=t[rts[p]].v)DCSB

                 printf("%d\n",calc(rts[p],q));

             }

         }

     }

     return ;

 }

巴特西

（2016北京集训十）【xsy1530】小Q与内存

代码：

最新文章

热门文章