about 3 years ago

完结动态树专题,好吧,表示这题其实并没有考验到太多的LCT的能力,不过滋瓷思维题啊

我们知道,LCT是不能进行批量修改的本来常数就大,这样一搞稳被卡飞啊,但是我们又知道LCT的森林维护是非常灵活滋瓷的,所以我们可以考虑对于所有操作存下来,离线处理
把所有操作存下来后,我们考虑相邻两棵树的差异,用LCT直接维护即可感觉是水题啊 (逃)

#include <bits/stdc++.h>

using namespace std;

#define REP(i, a, b) for (int i = (a), i##_end_ = (b); i <= i##_end_; ++i)
#define debug(...) fprintf(stderr, __VA_ARGS__)
#define mp make_pair
#define x first
#define y second
#define pb push_back
#define SZ(x) (int((x).size()))
#define ALL(x) (x).begin(), (x).End()

template<typename T> inline bool chkmin(T &a, const T &b) { return a > b ? a = b, 1 : 0; }
template<typename T> inline bool chkmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; }

typedef long long LL;

#define getchar getchar_unlocked

inline int read()
{
    register int c = getchar(), sum(0), fg(1);
    while (c < '0' || c > '9') { if (c == '-') fg = -1; c = getchar(); }
    while (c >= '0' && c <= '9') sum = sum * 10 + c - '0', c = getchar();
    return sum * fg;
}

const int oo = 0x3f3f3f3f;

const int maxn = 100000, maxm = 400000;

struct LCT
{
    int pre[maxm + 5], ch[maxm + 5][2], size[maxm + 5], val[maxm + 5], lval[maxm + 5];

#define L ch][0
#define R ch][1

    inline bool is_root(const int &x) { return !x || (x[pre][L] != x && x[pre][R] != x); }

    inline void push_up(const int &x)
    {
        x[lval] = x[size] = x[val];
        if (x[L]) x[lval] = x[L][lval], x[size] += x[L][size];
        if (x[R]) x[size] += x[R][size];
    }

    inline void rotate(const int &x)
    {
        int y = x[pre], T = x == y[R];
        y[ch][T] = x[ch][!T];
        if (x[ch][!T]) x[ch][!T][pre] = y;
        x[pre] = y[pre];
        if (y == y[pre][L]) y[pre][L] = x;
        if (y == y[pre][R]) y[pre][R] = x;
        y[pre] = x;
        x[ch][!T] = y;
        push_up(y);
    }

    inline void splay(const int &x)
    {
        while (!is_root(x))
        {
            int y = x[pre], z = y[pre];
            if (!is_root(y)) rotate((y == z[L]) ^ (x == y[L]) ? x : y);
            rotate(x);
        }
        push_up(x);
    }

    inline int access(const int &x)
    {
        for (splay(x), x[R] = 0, push_up(x); x[pre]; splay(x))
        {
            splay(x[pre]);
            x[pre][R] = x;
            push_up(x[pre]);
        }
        return x;
    }

    inline void cut(const int &x)
    {
        access(x), splay(x);
        x[L] = x[L][pre] = 0;
        push_up(x);
    }

    inline void link(const int &x, const int &y, const int &w)
    {
        splay(y);
        y[pre] = x;
        y[val] = w;
        push_up(y);
    }

    inline int query(const int &x, const int &y)
    {
        int cnt = 0, flag = 1;
        access(x), access(y), splay(x);
        if (x[pre]) cnt += x[size], flag &= x[lval];
        access(x), splay(y);
        if (y[pre]) cnt += y[size], flag &= y[lval];
        if (!flag) cnt += 2;
        return cnt;
    }
}t;

struct Query
{
    int x, y;

    Query(const int &_x = 0, const int &_y = 0): x(_x), y(_y) { }
}que[maxm + 5];

int l[maxm + 5], r[maxm + 5], ans[maxm + 5], to[maxm + 5], id[maxm + 5], start, End, P = 1, C = 2, Q = 0;

vector <int> I[maxn + 5], D[maxn + 5], q[maxn + 5];

int N, M;

int main()
{
#ifndef ONLINE_JUDGE
 freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
 N = read(), M = read();
    l[1] = 1, r[1] = N, id[1] = 1;
    REP(i, 1, M)
    {
        int type = read();
        if (type == 0)
        {
            id[++P] = ++C;
            l[P] = read(), r[P] = read();
        }
        if (type == 1)
        {
            start = read(), End = read(), to[++C] = read();
            chkmax(start, l[to[C]]);
            chkmin(End, r[to[C]]);
            if (start <= End) I[start].pb(C), D[End].pb(C);
        }
        if (type == 2)
        {
            ++Q;
            start = read(), que[Q].x = read(), que[Q].y = read();
            q[start].pb(Q);
        }
    }
    t.link(1, 2, 1);
    REP(i, 3, C) t.pre[i] = i - 1;
    REP(i, 1, N)
    {
        for (auto j : I[i]) t.cut(j), t.link(id[to[j]], j, 1);
        for (auto j : q[i]) ans[j] = t.query(id[que[j].x], id[que[j].y]);
        for (auto j : D[i]) t.cut(j), t.link(j - 1, j, 0);
    }
    REP(i, 1, Q) printf("%d\n", ans[i]);
    return 0;
}
← 后缀自动机 (Suffix Automaton) ZJOI2010 & BZOJ1834 网络扩容 (最大流 & 最小费用最大流) →