题解：AT_abc253_g [ABC253G] Swap Many Times

Elairin176 · 2024-12-20 21:46:14 · 题解

洛谷 Link
Atcoder Link

前言

为啥题解清一色是找性质呢？其实这道题可以直接暴力 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 实现。这里仅展示循环移位部分，其他部分请读者自行实现：

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;
  }
}