【题解】[Tjoi2016&Heoi2016] 排序 线段树合并+分裂 BZOJ – 4552

传送门_(:зゝ∠)_

又觉得别人线段树合并分裂丑要自己写，又写了半天（关键自己写的也挺丑的）

首先对于每一个排过序的块，它的值都是有序的，因此每一块连续的排序块我们都用一个权值线段树维护其内含的值

初始的时候就是 $n$个块，每个块一个元素

然后对一段区间排序就是把这个区间内的块都合并起来，就是权值线段树的合并

当然有可能区间端点在块的内部，就需要把块分裂开，就是权值线段树的分裂

每个块所代表的区间位置得用一个平衡树维护，偷懒就用了 set，跑得还挺快的

复杂度 $O(m log n)$

#include <bits/stdc++.h>

#define NS (100005)
#define FIR first
#define SEC second

using namespace std;

typedef pair<int, int> PII;
typedef pair<int, bool> PIB;
typedef map<int, PIB>::iterator itr;

template<typename _Tp> inline void IN(_Tp& dig)
{
    char c; bool flag = 0; dig = 0;
    while (c = getchar(), !isdigit(c)) if (c == '-') flag = 1;
    while (isdigit(c)) dig = dig * 10 + c - '0', c = getchar();
    if (flag) dig = -dig;
}

int n, m;

map<int, PIB> mp;

struct N {int l, r, sz;} e[NS * 60];

int sz;

stack<int> rub;

int New()
{
    int tmp;
    if (!rub.empty()) tmp = rub.top(), rub.pop();
    else tmp = ++sz;
    memset(&e[tmp], 0, sizeof(N));
    return tmp;
}

void pup(int a) {e[a].sz = e[e[a].l].sz + e[e[a].r].sz;}

int Mix(int x, int y)
{
    if (!x && !y) return 0;
    int a = New();
    e[a].l = x, e[a].r = y, pup(a);
    return a;
}

int Create(int d, int L, int R)
{
    int a = New();
    if (L == R) {e[a].sz = 1; return a;}
    int Mid = (L + R) >> 1;
    if (d <= Mid) e[a].l = Create(d, L, Mid);
    else e[a].r = Create(d, Mid + 1, R);
    pup(a);
    return a;
}

int Merge(int a, int b)
{
    if (!a || !b) return (a | b);
    e[a].l = Merge(e[a].l, e[b].l);
    e[a].r = Merge(e[a].r, e[b].r);
    e[a].sz += e[b].sz, rub.push(b);
    return a;
}

PII Split(int a, int d)
{
    if (!a) return PII(0, 0);
    if (e[a].sz == d) return PII(a, 0);
    if (!d) return PII(0, a);
    if (d <= e[e[a].l].sz)
    {
        PII tmp = Split(e[a].l, d);
        tmp = PII(Mix(tmp.FIR, 0), Mix(tmp.SEC, e[a].r));
        rub.push(a);
        return tmp;
    }
    PII tmp = Split(e[a].r, d - e[e[a].l].sz);
    tmp = PII(Mix(e[a].l, tmp.FIR), Mix(0, tmp.SEC));
    rub.push(a);
    return tmp;
}

int Query(int d, int L, int R, int a)
{
    if (L == R) return L;
    int Mid = (L + R) >> 1;
    if (e[e[a].l].sz > d) return Query(d, L, Mid, e[a].l);
    return Query(d - e[e[a].l].sz, Mid + 1, R, e[a].r);
}

itr Find(int x)
{
    itr res = mp.lower_bound(x);
    if (res == mp.end() || res->FIR > x) res--;
    return res;
}

int main(int argc, char const* argv[])
{
    IN(n), IN(m);
    for (int i = 1, a; i <= n; i += 1)
        IN(a), mp[i] = PIB(Create(a, 0, n), 0);
    itr x, y;
    for (int i = 1, o, l, r; i <= m; i += 1)
    {
        IN(o), IN(l), IN(r);
        x = Find(l);
        if (x->FIR != l)
        {
            PII tmp;
            if (x->SEC.SEC)
            {
                tmp = Split(x->SEC.FIR, e[x->SEC.FIR].sz - l + x->FIR);
                swap(tmp.FIR, tmp.SEC);
            }
            else tmp = Split(x->SEC.FIR, l - x->FIR);
            x->SEC.FIR = tmp.FIR, mp[l] = PIB(tmp.SEC, x->SEC.SEC);
        }
        y = Find(r);
        if (e[y->SEC.FIR].sz != r - y->FIR + 1)
        {
            PII tmp;
            if (y->SEC.SEC)
            {
                tmp = Split(y->SEC.FIR, e[y->SEC.FIR].sz - r + y->FIR - 1);
                swap(tmp.FIR, tmp.SEC);
            }
            else tmp = Split(y->SEC.FIR, r - y->FIR + 1);
            y->SEC.FIR = tmp.FIR, mp[r + 1] = PIB(tmp.SEC, y->SEC.SEC);
        }
        x = mp.find(l), y = mp.upper_bound(r);
        int a = 0;
        for (itr j = x; j != y; j++)
            a = Merge(a, j->SEC.FIR);
        mp.erase(x, y), mp[l] = PIB(a, o);
    }
    int q;
    IN(q), x = Find(q), q -= x->FIR - 1;
    if (x->SEC.SEC) q = e[x->SEC.FIR].sz - q + 1;
    printf("%d\n", Query(q - 1, 0, n, x->SEC.FIR));
    return 0;
}