【NOIP2017】列队 splay

当年太菜了啊，连$60$分的暴力都没拿满，只打了一个$30$分的。

考虑到这题最多只会询问到$30W$个点，且整个矩阵会去到$30W\times 30W$，显然不能将所有的点存下来。

对于每一行（除最右侧的数）我们维护一个$splay$，存储该位置的值，考虑到矩阵很大肯定不能全部开下，我们用一个节点存储一个区间（详情见代码）

这样会发现最右侧一列被吃了，所以我们还要维护一个$splay$去存储这一列的数。

对于一组询问$（x,y）$，当$y=m$时，那么显然直接在最右侧的$slpay$上删去某个位置的值，然后丢到这个$splay$的末尾即可。

当$y≠m$时，我们就在第x课splay中将包含有y这个数的区间拎出来，砍成三段（详情见代码），从这个$splay$中删去这个数字，然后重复$y=m$时所做的操作。

这么做的时间复杂度是$O(m\ log\ n+n\ log\ m+q\ log\ n+q\ log\ m)$，常数有点大但反正过了。

代码貌似不短qwq，可能是我的写法比较垃圾

 #include<bits/stdc++.h>

 #define M 500005

 #define L long long

 #define lc(x) ch[x][0]

 #define rc(x) ch[x][1]

 using namespace std;

 int ch[M*][]={},siz[M*]={},fa[M*]={},cnt[M*]={};L a[M*]={};

 int rt[M]={},rty=,use=;

 L n,m,q,numuse;

 void pushup(int x){siz[x]=siz[lc(x)]+siz[rc(x)]+cnt[x];}

 void rotate(int x,int &k){

     int y=fa[x],z=fa[y];

     int l=lc(y)!=x,r=l^;

     if(y==k) k=x;

     else{

         if(lc(z)==y) lc(z)=x;

         else rc(z)=x;

     }

     fa[x]=z; fa[y]=x; fa[ch[x][r]]=y;

     ch[y][l]=ch[x][r]; ch[x][r]=y;

     pushup(y); pushup(x);

 }

 void splay(int x,int &k){

     while(x!=k){

         int y=fa[x],z=fa[y];

         if(y!=k){

             if((lc(z)==y)^(lc(y)==x)) rotate(x,k);

             else rotate(y,k);

         }

         rotate(x,k);

     }

 }

 int find(int x,int k){

     if(!x) return ;

     if(k<=siz[lc(x)]) return find(lc(x),k);

     if(k<=siz[lc(x)]+cnt[x]) return x;

     return find(rc(x),k-siz[lc(x)]-cnt[x]);

 }

 void ins(int &x,int k,int id){

     if(!x) {x=id; pushup(id); return;}

     if(k<=siz[lc(x)]) ins(lc(x),k,id),fa[lc(x)]=x;

     else ins(rc(x),k-siz[lc(x)]-cnt[x],id),fa[rc(x)]=x;

     pushup(x);

 }

 void merge(int x,int y,int &rt){

     //合并两个splay

     if(!x) {rt=y; return;}

     if(!y) {rt=x; return;}

     rt=x; fa[x]=;

     while(rc(x)) x=rc(x);

     rc(x)=y; fa[y]=x;

     splay(y,rt);

 }

 int query(int x,int y){

     //询问x,y位置的值，并且从splay中分离出来

     int now=find(rt[x],y);

     if(!now) return ;

     splay(now,rt[x]);//找出点的位置

     if(cnt[now]==) return now;

     int lch=lc(now),rch=rc(now);

     int cntl=y-siz[lc(now)];

     if(cntl-){

         use++;

         a[use]=a[now];

         cnt[use]=cntl-;

         lc(use)=lc(now); fa[lc(use)]=use;

         lc(now)=use; fa[use]=now;

         pushup(use);

     }

     a[now]+=cntl-; cnt[now]-=cntl-;

     if(cnt[now]>){

         use++;

         a[use]=a[now]+;

         cnt[use]=cnt[now]-;

         rc(use)=rc(now); fa[rc(use)]=use;

         rc(now)=use; fa[use]=now;

         pushup(use);

     }

     cnt[now]=;

     pushup(now);

     return now;

 }

 int main(){

 //    freopen("in.txt","r",stdin);

 //    freopen("out.txt","w",stdout);

     cin>>n>>m>>q;

     numuse=n*m;

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

         rt[i]=++use;

         a[use]=(i-)*m+;

         cnt[use]=siz[use]=m-;

         a[++use]=i*m; cnt[use]=;

         ins(rty,i-,use);

         splay(use,rty);

     }

     while(q--){

         int x,y; scanf("%d%d",&x,&y);

         int now=query(x,y),outy=;L outnum;

         if(now){

             outnum=a[now];

             merge(lc(now),rc(now),rt[x]);

         }else outy=;

         now=find(rty,x);

         splay(now,rty);

         if(outy) outnum=a[now];

         merge(lc(now),rc(now),rty);

         lc(now)=rc(now)=;

         if(outy==){

             ins(rt[x],m-,now);

             splay(now,rt[x]);

         }

         a[++use]=outnum; cnt[use]=;

         ins(rty,n-,use); splay(use,rty);

         printf("%lld\n",outnum);

     }

 }

巴特西

【NOIP2017】列队 splay

最新文章

热门文章