国际惯例的题面:

这种维护排序序列，严格大于的进行操作的题都很套路......

我们按照[0,k],(k,2k],(2k,inf)分类讨论一下就好。

显然第一个区间的不会变化，第二个区间的会被平移进第一个区间，第三个区间的相对大小不会变化。

于是我们直接把第二个区间拆了重构，一个一个插入第一个区间即可。因为每次这样做最少减半，所以每个元素只会被重构log次，复杂度nlog^2n。

这种按照值域分离区间的操作，非旋转treap实现起来是最简单的......

然而第一次写非旋转treap还是出了一点问题，注意它的插入是通过按照值域分裂，新建点，再进行两次合并实现的。直接插入复杂度不对。

另外区间值域存在重合的情况两个treap不能直接合并......

我写的判定size的版本复杂度好像不对(不如暴力快？)，于是只好预先生成fix值。

代码:

1 #include
      
        2 #include
       
         3 #include
        
          4 const int maxn=1e5+1e2; 5  6 typedef std::pair
         
           pii; 7 __inline pii mp(const int &x,const int &y) { return std::make_pair(x,y); } 8  9 int seq[maxn],sql;10 int stk[maxn],top;11 12 struct Treap {13     int lson[maxn],rson[maxn],lazy[maxn],val[maxn],siz[maxn],fix[maxn],cnt;14     15     inline void init(int n) {16         for(int i=1;i<=n;i++) fix[i] = i;17         std::random_shuffle(fix+1,fix+1+n);18     }19     inline void apply(int pos,int x) {20         if(pos) lazy[pos] += x , val[pos] -= x;21     }22     inline void push(int pos) {23         if( lazy[pos] ) apply(lson[pos],lazy[pos]) , apply(rson[pos],lazy[pos]) , lazy[pos] = 0;24     }25     inline void maintain(int pos) {26         siz[pos] = siz[lson[pos]] + siz[rson[pos]] + 1;27     }28 29     inline pii split(int pos,int dv) { // left is <= , right is > .30         if( !pos ) return mp(0,0);31         push(pos);32         if(  dv < val[pos] ) {33             pii spl = split(lson[pos],dv);34             lson[pos] = spl.second , maintain(pos);35             return mp(spl.first,pos);36         } else {37             pii spr = split(rson[pos],dv);38             rson[pos] = spr.first , maintain(pos);39             return mp(pos,spr.second);40         }41     }42     inline int merge(int x,int y) {43         if( !x || !y ) return x | y;44         push(x) , push(y);45         if( val[x] > val[y] ) std::swap(x,y);46         if( fix[x] > fix[y] ) { // siz[x] is bigger .47             lson[y] = merge(lson[y],x) , maintain(y);48             return y;49         } else {50             rson[x] = merge(rson[x],y) , maintain(x);51             return x;52         }53     }54     inline void dfs(int pos) {55         if( !pos ) return;56         seq[++sql] = val[pos] , push(pos);57         dfs(lson[pos]) , dfs(rson[pos]);58         lson[pos] = rson[pos] = siz[pos] = 0 , stk[++top] = pos;59     }60     inline int kth(int pos,int k) { // return the kth value .61         if( k == siz[lson[pos]] + 1 ) return val[pos];62         return push(pos) , k <= siz[lson[pos]] ? kth(lson[pos],k) : kth(rson[pos],k-siz[lson[pos]]-1);63     }64     inline void insert(int &root,int x) {65         val[++cnt] = x , siz[cnt] = 1;66         pii sp = split(root,x);67         root = merge(sp.first,cnt) , root = merge(root,sp.second);68     }69     inline void reinsert(int &root,int x) {70         int cur = stk[top--];71         val[cur] = x , siz[cur] = 1;72         pii sp = split(root,x);73         root = merge(sp.first,cur) , root = merge(root,sp.second);74     }75     76 }tp;77 78 int main() {79     static int n,m,root,rtl,rtm,rtr;80     scanf("%d%d",&n,&m) , tp.init(n);81     for(int i=1,t;i<=n;i++) scanf("%d",&t) , tp.insert(root,t);82     for(int i=1,o,x;i<=m;i++) {83         scanf("%d%d",&o,&x);84         if( o == 1 ) printf("%d\n",tp.kth(root,x));85         else if( o == 2 ) {86             pii sp = tp.split(root,x);87             rtl = sp.first , sp = tp.split(sp.second,x<<1);88             rtm = sp.first , rtr = sp.second;89             sql = 0 , tp.dfs(rtm) , tp.apply(rtr,x);90             for(int i=1;i<=sql;i++) tp.reinsert(rtl,seq[i]-x);91             root = tp.merge(rtl,rtr);92         }93     }94     return 0;95 }
         
        
       
      

Thupc被拒了好气啊！我们队可是有yzy大爷的！(即使这样都被拒了，一看就是我太菜了)

ありのままでいればいつも

只要坚守自我维持现状

あるべき私かここにいると

自己希望成为的样貌就存在于此

信じてまた 新しい夢を

不要放弃希望 崭新的梦想

精一杯描き出せばいい

再次奋力地去描绘就好

そう気づき始めたよ私

是啊 而我开始意识到

みんなとただ笑ってる未来を

大家单纯地绽放笑容的未来

夢見て

诚心盼望