建议加强数据并撤下题解

P3391 【模板】文艺平衡树

whhsteven @ 2022-11-20 13:40:37

本人在浏览题解区时发现 这篇题解 是不使用 splay 树但是采用了将区间左右端点旋转到位后打标记的做法的唯一一篇。

具体地，他是先建出类似线段树的结构，然后每次修改时，将 l - 1 旋转到根，将 r + 1 旋转到根下面，并给 r + 1 的左儿子打上标记。

正确性没有问题。但是复杂度对不对呢？这样的数据可以将其卡掉：

区间长度 10^5，翻转操作次数 10^5，前 5 \times 10^4 次第 i 次翻转区间 [2i - 1, 2i]，后 5 \times 10^4 次第 i + 5 \times 10^4 次翻转区间 [2i - 1, 2i]。

实测这篇题解的代码在我的机子上跑这组数据的时间稳定在 20 秒以上，这是比较符合没有完全卡满的 O(n^2) 复杂度的表现的。

实际上，通过输出树的形态可以发现，在执行完前 5 \times 10^4 次操作后，树的形态已经成了高度为 O(n) 的左偏链挂单点了。

by whhsteven @ 2022-11-20 13:41:53

在我机子上测试时的编译选项是 -std=c++14 -O2，并已开够栈。

by whhsteven @ 2022-11-20 13:43:06

数据生成器：

#include<bits/stdc++.h>

using namespace std;

namespace acah
{
    ofstream gen("data.in");

    int work()
    {
        gen << "100000 100000\n";
        for(int i = 1; i <= 50000; i++) gen << i * 2 - 1 << ' ' << i * 2 << '\n';
        for(int i = 1; i <= 50000; i++) gen << i * 2 - 1 << ' ' << i * 2 << '\n';
        cout << "Generated!";

        return 0;
    }
}

int main() {return acah::work();}

by whhsteven @ 2022-11-20 13:49:14

@dottle

@小粉兔

by Konjac_16 @ 2022-11-21 07:29:58

@dottle

by lcyxds @ 2022-11-28 15:34:57

看了下题解好像是由来已久的 Spaly 树？Spaly 能过绝大多数平衡树题出题人都不往这个方向卡（

|