洛谷P3960 [NOIP2017] 列队

数据结构题还是挺好玩的

注意到每次只变动三个点：（x，y），（x，m），（n，m），其他地方都是整块移动。

可以开n+1个线段树，前n个存每行前m-1个人，最后一个存第m列的人。

(x,y)位置的人出列时，抽出该位置的标号，加到第n+1个线段树的最后面去，抽出第n+1个线段树的第x个元素（即(x,m)，加到第x个线段树的最后面去。

↑实现这一操作，可以记线段树的size，每次二分查询树上第k个元素即可确定位置。

↑当然树不可能全建出来，需要动态开点。尚未申请的结点，size直接用$ r-l+1 $计算。

写到一半想到不需要专门抽出来，只需要记录该行到该位置为止抽出过a个数，找(x,y)时实际找(x,y+a)即可。可以开个vector什么的存新加到队伍最右边的人。

这样的话更加方便&优美，而且可以用树状数组写，代码量也减小了。

但是看着自己写了一大半的代码不舍得丢，还是强行按原计划敲完了。

————

老年退役选手连NOIP题都做不来了。做这题成功遇到了数组开小，变量写混，初始化错误，输出错误等等问题，调了好久。

不开心QAQ

————

 #include<iostream>

 #include<cstdio>

 #define LL long long

 using namespace std;

 const int mxn=;

 struct node{

     int sz,lc,rc;

     LL mk;

 }t[mxn<<];

 int cnt=,mod=;

 int root[mxn];

 int n,N,m,Q;

 inline int getsz(int l,int r,int rt){

     if(rt)return t[rt].sz;

     return r-l+;

 }

 void pushup(int l,int r,int rt){

     int tmp=;

     int mid=(l+r)>>;

     tmp+=getsz(l,mid,t[rt].lc);

     tmp+=getsz(mid+,r,t[rt].rc);

     t[rt].sz=tmp;

     return;

 }

 int anspos;

 int query(int k,int l,int r,int &rt){

     if(!rt){

         rt=++cnt;

         t[rt].sz=r-l+;

     }

     if(l==r){

         if(!t[rt].mk){//计算标号

             if(mod==n+)t[rt].mk=(LL)l*m;

             else t[rt].mk=(LL)(mod-)*m+l;

         }

         anspos=l;

         return rt;

     }

     int mid=(l+r)>>,tmp=getsz(l,mid,t[rt].lc);

     if(k<=tmp)

         return query(k,l,mid,t[rt].lc);

     else return query(k-tmp,mid+,r,t[rt].rc);

 }

 void update(LL v,int p,int l,int r,int &rt){

     if(!rt){

         rt=++cnt;

         t[rt].sz=r-l+;

     }

     if(l==r){

         t[rt].mk=v;

         if(!v){//del

             t[rt].sz=;

         }

         else t[rt].sz=;

         return;

     }

     int mid=(l+r)>>;

     if(p<=mid)update(v,p,l,mid,t[rt].lc);

     else update(v,p,mid+,r,t[rt].rc);

     pushup(l,r,rt);

     return;

 }

 void info(int l,int r,int rt){

     printf("  %d %d rt:%d sz:%d\n",l,r,rt,getsz(l,r,rt));

     if(!rt)return;

     if(l==r)return;

     int mid=(l+r)>>;

     info(l,mid,t[rt].lc);

     info(mid+,r,t[rt].rc);

     return;

 }

 int main(){

 //    freopen("2017phalanx.in","r",stdin);

 //    freopen("2017phalanx.out","w",stdout);

     int i,j,x,y,tmp;

     LL tmp2;

     scanf("%d%d%d",&n,&m,&Q);

     N=max(max(n,m),Q)<<;

     while(Q--){

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

         if(y==m){

             mod=n+;

             tmp=query(x,,N,root[n+]);

             tmp2=t[tmp].mk;

             printf("%lld\n",t[tmp].mk);

             update(,anspos,,N,root[n+]);

             tmp=query(n,,N,root[n+]);

             update(tmp2,anspos,,N,root[n+]);

         }

         else{

 //            printf("  in\n");

             mod=x;

             tmp=query(y,,N,root[x]);

             tmp2=t[tmp].mk;

             printf("%lld\n",t[tmp].mk);

             update(,anspos,,N,root[x]);//出队

 //            printf("anspos:%d\n",anspos);

             //

             mod=n+;

             tmp=query(n+,,N,root[n+]);

             update(tmp2,anspos,,N,root[n+]);

 //            printf("UPD: mk:%d pos:%d\n",tmp2,anspos);

             //

             tmp=query(x,,N,root[n+]);

             tmp2=t[tmp].mk;

 //            printf("bu:%d anspos:%d\n",tmp2,anspos);

             update(,anspos,,N,root[n+]);

             mod=x;

             tmp=query(m-,,N,root[x]);

             update(tmp2,anspos,,N,root[x]);

             //

         }

 //        info(1,N,root[n+1]);

     }

     return ;

 }

巴特西

洛谷P3960 [NOIP2017] 列队

最新文章

热门文章