题解 P3391 一种特殊的做法（【模板】文艺平衡树）

· · 题解

题目链接

题目大意

一个序列，初始是 1 \sim n，q 次操作，每次反转一段区间，求最终序列。1 \le n,q \le 10^5

实际上这题可以用普及组做法做，也就是 Treap，Splay，块状链表都不用，而且代码非常短，不压也可以进 1KB，稍微压压就是大约 800B 甚至更少。

前置芝士

毕竟是普及组做法，肯定很简单：

没了

进入正题

维护一个双链表，一开始就是 1 - 2 - 3 - \dots - n

每次操作，直接把对应的 [l,r] 区间指针改一改就好了。

不过，众所周知，链表想要找到一个下标对应的结点是 O(n) 的，导致退化为暴力复杂度。

然鹅，如果要去维护下标对应节点，又和直接维护序列完全没区别了，所以，要换一条路走。

观察翻转一段区间后，下标对应节点的变化：

假设翻转的区间为 [l,r]，那么下面讨论下标 x 对应节点在翻转前的下标

  1. l \le x \le r$，也就是说 $x$ 被翻转区间覆盖了，那么原下标为 $l+r-x
  2. x \lt l$ 或 $x>r$，那么原下标还是 $x

于是，用数组来存双链表，直接计算出 l,r 分别的原下标即可。

但是，新的问题出现了，想要找到对应的原下标，需要把前面的操作倒叙遍历一遍，很可惜，这样做一遍还是 O(n) 的。

不过，如果把双链表重构（就是直接把现在的序列重新存进双链表）一下，那么接下来寻找原下标时就只需要遍历重构后的部分即可。

重构操作是 O(n) 的，而重构后第 b 次操作需要用 O(b) 的时间找到原下标。

用分块思想，每 B 个操作为一块，每块结束后重构链表，那么时间复杂度是 O(qB+\frac{q}{B} \times n) 的，在 B=O(\sqrt n) 时取最小值 O(q \sqrt n)

最后一个问题，就是翻转的时候，会导致左右指针有可能会相反，导致后续操作的混乱。

解决方式很简单，不局限于左右指针的区别，直接当成地位相同的指针即可，直接在往前找原下标的时候顺便判断指针方向，如果被翻转的次数为偶数则指针方向不变，否则相反即可。

上面一行的证明还是分类讨论：

再次假设翻转的区间为 [l,r]，那么下面讨论下标 x 对应节点的左右指针是否相反。

  1. 如果 x=l 或 x=r，不妨 x=l，x 原本的右指针为 u，r 原本的左指针为 v，那么有 x 现在的左右指针分别为 v,u，而实际上 x 的左右指针应该分别为 u,v，于是指针相反
  2. 如果 l \lt x \lt r，那么 x 现在的指针没有发生改变，实际上应该反过来，于是指针相反
  3. 如果 x=l-1 或 x=r+1，那么 x 对应指针改变，但方向不变，于是指针方向不受影响
  4. 如果 x \lt l-1 或 x \gt r+1，那么 x 不受影响

重构时由于需要从双链表的头部开始重构，所以操作时需要维护头部，这部分很简单，直接判断是否翻转了头部，修改即可。

重构时还需要知道往哪个指针走，但是如果暴力判断方向会导致重构变成 O(nB)=O(n \sqrt n)，时间复杂度炸掉，不过这一步也很简单，直接记录从哪个节点过来的，访问不是那个节点的另一个节点即可。

总时间复杂度 O(q \sqrt n)，空间复杂度 O(n)，常数比较小，能轻松 A 掉。

AC 代码：

#include<bits/stdc++.h>
using namespace std;
int n,q,b,m,a[100009],g[100009],h[100009],s[100009],e,l,r,u[319],v[319],t,o,*ul,*ur,vl,vr;
bool ll,rr;
inline void gt(int x,int* xx,bool* r){
    bool res=0;
    for(int i=t-1;~i;--i) if(u[i]<=x&&x<=v[i]) res=!res,x=u[i]+v[i]-x;
    *r=res,*xx=x;
}
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n>>q,b=sqrt(n)+1,e=1,iota(a+1,a+n+1,1),iota(g+1,g+n,2),iota(h+2,h+n+1,1);
    for(int i=1;i<=q;++i){
        cin>>l>>r,u[t]=l,v[t]=r,++m;
        gt(l,&vl,&ll),gt(r,&vr,&rr);
        e==vl?(e=vr):e==vr&&(e=vl),ul=(ll?g:h)+vl,ur=(rr?h:g)+vr,*ul&&(*((g[*ul]==vl?g:h)+*ul)=vr),*ur&&(*((g[*ur]==vr?g:h)+*ur)=vl),swap(*ul,*ur);//翻转双链表vl->vr
        ++t;
        if(m==b||i==q){
            t=m=o=0;
            for(int j=1;j<=n;++j,e=(g[e]==o?(o=e,h[e]):(o=e,g[e]))) s[j]=a[e];
            memcpy(a+1,s+1,n<<2),e=1,iota(g+1,g+n,2),iota(h+2,h+n+1,1),g[n]=h[1]=0;
        }
    }
    for(int i=1;i<=n;++i) cout<<a[i]<<" ";
    return 0;
}

AC 记录 933B（没有压代码）