题解：AT_abc253_g [ABC253G] Swap Many Times

前言

为啥题解清一色是找性质呢？其实这道题可以直接暴力 ds 的，就是复杂度劣一些。

解法

我们注意到，一段形如

(i,l),(i,l+1),\dots,(i,r)

的操作等价于对

a_i

和

a_l,a_{l+1},\dots,a_r

作循环右移。形式化地：

$a'_i=a_r$
$a'_l=a_i$
$a'_p=a_{p-1}(l<p\le r)$

那么我们对于这个操作直接上平衡树就行了，复杂度

\mathcal{O}(n\log n)

。
这里我采用 FHQ Treap 实现。这里仅展示循环移位部分，其他部分请读者自行实现：

CPP

ll s=0,l,r;
for(int i=1;i<=n;i++){
  s+=n-i;
  if(s>=lp){
    l=n-s+lp;r=n;
    if(s>=rp) r=n-s+rp;
    //i l~r
    int r1,r2,r3,r4,r5,r6;
    split(r1,r2,l-1,rt);
    split(r2,r3,r-l+1,r2);
    split(r2,r6,r-l,r2);
    split(r1,r4,i-1,r1);
    split(r4,r5,1,r4);
    //r1 -> 1~i-1  r4 -> i r5 -> i+1~l-1
    //r2 -> l~r-1 r6 -> r r3 -> r+1~n
    rt=merge(r1,r6);
    rt=merge(rt,r5);
    rt=merge(rt,r4);
    rt=merge(rt,r2);
    rt=merge(rt,r3);
    if(s<rp) lp=s+1;
    else break;
  }
}

题解：AT_abc253_g [ABC253G] Swap Many Times

文章操作

前言

解法

相关推荐

评论

题解：AT_abc253_g [ABC253G] Swap Many Times