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

Margatroid · 2017-10-14 22:00:10 · 题解

看了一圈发现大家都是用的很清真的splay，这里介绍一种用STL强行混分的做法

rope是STL内置的一颗平衡树，详细的文档可以见这里虽然是洋文版的

rope一般用来维护字符串，当然，对于这个题，我们让它维护序列

rope相比与string，可以实现高效的分裂和合并，我们可以利用这个性质来进行一波操作

但是。。它封装的这么严，怎么打标记呢？

其实是不用打标记的

我们维护一正一反两个rope，翻转操作就是交换它们的对应区间

然后就没有了。。缺点是常数很大。。。

下面是代码qwq

//
// Created by margatroid on 17-9-17.
//

#include<bits/stdc++.h>
#include<ext/rope>
using namespace std;
using namespace __gnu_cxx;
inline char getc()
{
    static char buf[1 << 18], *fs, *ft;
    return (fs == ft && (ft = (fs = buf) + fread(buf, 1, 1 << 18, stdin)), fs == ft) ? EOF : *fs++;
}
inline int gn()
{
    register int k = 0, f = 1;
    register char c = getc();
    for(; !isdigit(c); c = getc()) if(c == '-') f = -1;
    for(; isdigit(c); c = getc()) k = k * 10 + c - '0';
    return k * f;
}
rope<int> str, rstr;
int n, m;
inline void rev(int st, int ed)
{
    if (st >= ed + 1) return;
    ed++;
    rope<int> tmp = str.substr(st + str.begin(), ed + str.begin());
    str = str.substr(0 + str.begin(), st + str.begin()) + rstr.substr(n - ed + rstr.begin(), n - st + rstr.begin()) + str.substr(ed + str.begin(), str.length() + str.begin());
    rstr = rstr.substr(rstr.begin(), n - ed + rstr.begin()) + tmp + rstr.substr(n - st + rstr.begin(), rstr.length() + rstr.begin());
}
int main()
{
    n = gn(), m = gn();
    for (int i = 1; i <= n; ++i)
        str.append(i), rstr.append(n - i + 1);
    for (int i = 1; i <= m; ++i)
    {
        int l, r;
        l = gn(), r = gn();
        rev(l - 1, r - 1);
    }
    for (int i = 0; i < str.length(); ++i)
        printf("%d ", str[i]);
    puts("");
}