Edison UVALive3488-白红宇

Edison UVALive3488

阅读量：5978 次

发布时间：2019-06-20

本文共 1116 字，大约阅读时间需要 3 分钟。

题目大意

有一个0~n-1的序列，有m次操作，操作包含三个元素：pl，len，ti，表示这个操作进行ti次，每次将从pl+1开始的len个元素移到序列头部。

分析

看到题不难想到使用平衡树将需移动部分切出来挂到顶部。本题我使用fhqtreap来实现，但需要注意的是对于挪动部分使用的split不再以节点值为关键字切割而改用它在树中的排名作为关键字。具体实现详见代码。注意输出格式！！！！！！！！

代码

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #include
               
                #include
                
                 #include
                 #include
                  
                   using namespace std;int root,son[1100000][2],a[1100000],rd[1100000],siz[1100000],cnt,n;inline void up(int x){siz[x]=siz[son[x][0]]+siz[son[x][1]]+1;}inline int bnode(int x){ siz[++cnt]=1; a[cnt]=x; rd[cnt]=rand(); return cnt;}inline int gk(int rt,int k){ while(1){ if(k<=siz[son[rt][0]])rt=son[rt][0]; else if(k==siz[son[rt][0]]+1)return rt; else k-=siz[son[rt][0]]+1,rt=son[rt][1]; }}inline void spt1(int rt,int k,int &x,int &y){ if(!rt)x=y=0; else { if(a[rt]<=k)x=rt,spt1(son[rt][1],k,son[rt][1],y); else y=rt,spt1(son[rt][0],k,x,son[rt][0]); up(rt); }}inline int mer(int x,int y){ if(!x||!y)return x+y; if(rd[x]

转载于:https://www.cnblogs.com/yzxverygood/p/9390741.html

你可能感兴趣的文章