题解 P3391【【模板】文艺平衡树】

· · 题解

大家好，我非常喜欢暴力数据结构，于是我就用分块过了这道题。

而且比大多数平衡树跑得快。

这个题对序列分块肯定是不可取的。

块状链表又难写又慢。

所以考虑对时间分块，根号重构。（虽然块状链表好像类似，但是我的做法好写得多）

考虑原序列经过几次翻转之后得到的序列，是由原序列的一些子区间，正序或者逆序拼成的，比如:

原序列：[1,2,3,4,5,6,7,8,9,10,11,12]

翻转 [5,11]：[1,2,3,4,11,10,9,8,7,6,5,12]

翻转 [1,7]：[9,10,11,4,3,2,1,8,7,6,5,12]

在原序列上的子区间是 [9,10,11]，[4,3,2,1]，[8,7,6,5]，[12]。

而且有一个非常好的性质就是每次操作最多增加常数个子区间。

因为对于上个状态的某个子区间，如果它和这次翻转的区间没有交，那么它不会动。

如果它被这次翻转的区间包含，那么它会被翻转，并且换个位置，数量不会增加。

如果它与这次翻转的相交，那么它会最多裂开成 3 个区间（即它包含翻转的区间的情况，别的情况都会裂开成两个），其中有一个区间被翻转，换位置，剩下的区间不动。

一个区间最多与 2 个不相交的区间相交且没有包含关系，所以每次最多增加两个区间。

回到这个题上，考虑维护每个子区间，而不是原序列。

每次修改暴力枚举所有子区间，看一下它们会变成什么，这个的复杂度是 O(\text{区间个数}) 的。

但是每次操作后都有可能增加几个子区间，到后面每次操作就趋近 O(n) 了，所以考虑根号重构。

也就是说，一旦当前区间个数超过了某个阈值 B，就 O(n) 求一下当前的序列，这样现在这个序列就又能用 1 个区间表示啦。

比如：

[1,2,3,4,5,6,7,8,9,10,11,12]

翻转 [4,10]

[1,2,3],[10,9,8,7,6,5,4],[11,12]

翻转 [7,10]

[1,2,3],[10,9,8],[4,5,6,7],[11,12]

翻转 [2,11]

[1],[11],[7,6,5,4],[8,9,10],[3,2],[12]

这时候觉得区间有点多，重构一下。

[1,11,7,6,5,4,8,9,10,3,2,12]

注意这个时候原序列已经没关系了，只用把当前序列表示成上一次重构时的一些子区间，正序或逆序拼成的。

翻转 [3,7]

[1,11],[8,4,5,6,7],[9,10,3,2,12]

翻转 [7,8]

[1,11],[8,4,5,6],[9],[7],[10,3,2,12]

这个做法的时间复杂度是 O(mB+\frac{m}{B}n) 的（因为每次操作要遍历 O(B) 个区间，每 B 个询问要 O(n) 求一边当前序列）

取 B=\sqrt{n} 时，时间复杂度达到 O(m\sqrt n)，而且常数非常小，实测 B\in [200,800] 的时候跑的速度都差不多。

具体实现的时候需要记一下每个子区间在当前序列的位置，以及它们在上一次重构时的位置，还有是否被取反。

分裂子区间的时候就直接加到后面。

重构的时候直接把所有区间都删了，换成 [1,n]。

代码（还挺好写的）：

#include <iostream>
using namespace std;
const int bl=400;//阈值大小
int a[100005],b[100005],cnt,n,q;//cnt表示子区间个数
struct node{//子区间
    int l1,l2,r2,f;//l1是原序列上左端点的位置，
    //l2,r2是现序列上的位置，f是是否翻转，由于r1-l1一定=r2-l2，所以r1就不记了
}s[405];
inline void rev(int l,int r){//翻转区间 [l,r]
    for(int i=1;i<=cnt;i++){//遍历所有子区间
        if(s[i].r2<l||s[i].l2>r) continue;//没有交直接跳过
        if(l>s[i].l2){//右边相交，要分裂
            if(!s[i].f) s[++cnt]={l-s[i].l2+s[i].l1,l,s[i].r2,0},s[i]={s[i].l1,s[i].l2,l-1,0};
            else s[++cnt]={s[i].l1,l,s[i].r2,1},s[i]={s[i].l1+s[i].r2-l+1,s[i].l2,l-1,1};
            //计算分裂完的两个区间的信息
        }
        if(r<s[i].r2){//左边相交，同理，代码上只是把l换成了r+1
            if(!s[i].f) s[++cnt]={r+1-s[i].l2+s[i].l1,r+1,s[i].r2,0},s[i]={s[i].l1,s[i].l2,r+1-1,0};
            else s[++cnt]={s[i].l1,r+1,s[i].r2,1},s[i]={s[i].l1+s[i].r2-r,s[i].l2,r,1};
        }
        if(s[i].r2<l||s[i].l2>r) continue;//分裂完不相交
        s[i].l2=r-s[i].l2+l,s[i].r2=r-s[i].r2+l,swap(s[i].l2,s[i].r2),s[i].f^=1;
        //计算翻转后区间的信息
    }
}
inline void qwq(){//重构
    for(int i=1;i<=cnt;i++){//把每个区间的值暴力赋过去
        if(s[i].f) for(int j=s[i].r2;j>=s[i].l2;j--) b[j]=a[s[i].l1++];
        else for(int j=s[i].l2;j<=s[i].r2;j++) b[j]=a[s[i].l1++];
    }
    cnt=1,s[cnt]={1,1,n,0},swap(a,b);//删掉原来所有区间
}
int main(int argc, char** argv) {
    scanf("%d%d",&n,&q);
    for(int i=1;i<=n;i++) a[i]=i;
    s[++cnt]={1,1,n,0};//一开始只有整个一个区间
    while(q--){
        int l,r;
        scanf("%d%d",&l,&r),rev(l,r);
        if(cnt>bl) qwq();//如果区间数大于阈值，就重构
    }
    qwq();//算最终的答案，相当于一次重构
    for(int i=1;i<=n;i++) printf("%d ",a[i]);
    return 0;
}

有评论的话我可能半年之内回不了，因为被禁言了/cy

有什么 bug 或者假了或者被踩了私信联系我

求过审