【BZOJ4825】【HNOI2017】單旋（線段樹，set）

Description

click me

Solution

手玩發現每次去最大、最小值也就是直接将該節點放到根節點，插入值就是将節點插入到該鍵值的前驅後繼中深度最大的那個的下方。

然後用

std::set

維護深度，用，線段樹維護深度即可。

Code

/**************************************
 * Au: Hany01
 * Prob: [BZOJ4825][HNOI2017] 單旋
 * Date: Apr 6th, 2018
 * Email: [email protected]
**************************************/

#include<bits/stdc++.h>

using namespace std;

typedef long long LL;
typedef pair<int, int> PII;
typedef vector<int> VI;
#define File(a) freopen(a".in", "r", stdin), freopen(a".out", "w", stdout)
#define rep(i, j) for (register int i = 0, i##_end_ = j; i < i##_end_; ++ i)
#define For(i, j ,k) for (register int i = (j), i##_end_ = (k); i <= i##_end_; ++ i)
#define Fordown(i, j, k) for (register int i = (j), i##_end_ = (k); i >= i##_end_; -- i)
#define Set(a, b) memset(a, b, sizeof(a))
#define SZ(a) ((int)(a.size()))
#define ALL(a) a.begin(), a.end()
#define pb(a) push_back(a)
#define mp(a, b) make_pair(a, b)
#define INF (0x3f3f3f3f)
#define INF1 (2139062143)
#define Mod (1000000007)
#define y1 wozenmezhemecaia 
#ifdef hany01
#define debug(...) fprintf(stderr, __VA_ARGS__)
#else
#define debug(...)
#endif

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

inline int read() {
    register char c_; register int _, __;
    for (_ = , __ = , c_ = getchar(); !isdigit(c_); c_ = getchar()) if (c_ == '-')  __ = -;
    for ( ; isdigit(c_); c_ = getchar()) _ = (_ << ) + (_ << ) + (c_ ^ );
    return _ * __;
}

const int maxn = ;

struct Opt { int ty, p; }opt[maxn];

int n, m, ls[maxn], fa[maxn], ch[maxn][], rt;
set<int> Set;

struct SegmentTree
{
    int tr[maxn << ], tag[maxn << ];

#define lc (t << 1)
#define rc (lc | 1)
#define mid ((l + r) >> 1)

    inline void maintain(int t) { tr[t] = tr[lc] + tr[rc]; }

    inline void pushdown(int t, int l, int r)
    {
        if (tag[t])
        {
            tag[lc] += tag[t], tag[rc] += tag[t];
            tr[lc] += tag[t] * (mid - l + ), tr[rc] += tag[t] * (r - mid);
            tag[t] = ;
        }
    }

    void update(int t, int l, int r, int x, int y, int dt)
    {
        if (x <= l && r <= y) {
            tr[t] += (r - l + ) * dt, tag[t] += dt;
            return ;
        }
        pushdown(t, l, r);
        if (mid >= x) update(lc, l, mid, x, y, dt);
        if (mid < y) update(rc, mid + , r, x, y, dt);
        maintain(t);
    }

    void reset(int t, int l, int r, int x, int dt)
    {
        if (l == r) { tr[t] = dt; return ; }
        pushdown(t, l, r);
        if (x <= mid) reset(lc, l, mid, x, dt);
        else reset(rc, mid + , r, x, dt);
        maintain(t);
    }

    int query(int t, int l, int r, int x)
    {
        if (l == r) return tr[t];
        pushdown(t, l, r);
        if (x <= mid) return query(lc, l, mid, x);
        else return query(rc, mid + , r, x);
    }

}st;

int main()
{
#ifdef hany01
    File("bzoj4825");
#endif

    m = read();
    For(i, , m)
        if ((opt[i].ty = read()) == ) ls[++ n] = opt[i].p = read();

    sort(ls + , ls +  + n);
    n = unique(ls + , ls +  + n) - ls - ;
    For(i, , m) if (opt[i].ty == ) opt[i].p = lower_bound(ls + , ls +  + n, opt[i].p) - ls;

    For(i, , m)
    {
        if (opt[i].ty == )
        {
            register int u = opt[i].p;
            Set.insert(u);
            if (SZ(Set) == ) st.reset(, , n, u, ), rt = u, puts("1");
            else if (Set.lower_bound(u) == Set.begin()) {
                int tmp = *Set.upper_bound(u);
                int dep = st.query(, , n, tmp);
                ch[tmp][] = u, fa[u] = tmp, st.reset(, , n, u, dep + );
                printf("%d\n", dep + );
            } else if (Set.upper_bound(u) == Set.end()) {
                int tmp = *--Set.lower_bound(u);
                int dep = st.query(, , n, tmp);
                ch[tmp][] = u, fa[u] = tmp, st.reset(, , n, u, dep + );
                printf("%d\n", dep + );
            } else {
                int tmp1 = *Set.upper_bound(u), tmp2 = *--Set.lower_bound(u);
                int dep1, dep2;
                dep1 = st.query(, , n, tmp1), dep2 = st.query(, , n, tmp2);
                if (dep1 > dep2) ch[tmp1][] = u, fa[u] = tmp1, st.reset(, , n, u, dep1 + );
                else ch[tmp2][] = u, fa[u] = tmp2, st.reset(, , n, u, dep2 + );
                printf("%d\n", max(dep1, dep2) + );
            }
        } else if (opt[i].ty == )
        {
            int u = *Set.begin();
            printf("%d\n", st.query(, , n, u));
            if (u == rt) continue;
            if (fa[u]) st.update(, , n, fa[u], n, );
            st.reset(, , n, u, );
            if (ch[u][]) fa[ch[u][]] = fa[u];
            if (fa[u]) ch[fa[u]][] = ch[u][];
            fa[u] = ;
            ch[u][] = rt, fa[rt] = u, rt = u;
        } else if (opt[i].ty == )
        {
            int u = *--Set.end();
            printf("%d\n", st.query(, , n, u));
            if (u == rt) continue;
            if (fa[u]) st.update(, , n, , fa[u], );
            st.reset(, , n, u, );
            if (ch[u][]) fa[ch[u][]] = fa[u];
            if (fa[u]) ch[fa[u]][] = ch[u][];
            fa[u] = ;
            ch[u][] = rt, fa[rt] = u, rt = u;
        } else if (opt[i].ty == )
        {
            int u = *Set.begin();
            printf("%d\n", st.query(, , n, u));
            if (rt == u) {
                Set.erase(Set.begin());
                rt = ch[u][];
                st.update(, , n, , n, -);
                continue;
            }
            if (ch[u][]) st.update(, , n, , fa[u] - , -);
            if (ch[u][]) fa[ch[u][]] = fa[u];
            ch[fa[u]][] = ch[u][];
            Set.erase(Set.begin());
        } else
        {
            int u = *--Set.end();
            printf("%d\n", st.query(, , n, u));
            if (rt == u) {
                Set.erase(--Set.end());
                rt = ch[u][];
                st.update(, , n, , n, -);
                continue;
            }
            if (ch[u][]) st.update(, , n, fa[u] + , n, -);
            if (ch[u][]) fa[ch[u][]] = fa[u];
            ch[fa[u]][] = ch[u][];
            Set.erase(*--Set.end());
            /*For(i, 1, n) cout << fa[i] << ' ';
            cout << endl;
            For(i, 1, n) cout << st.query(1, 1, n, i) << ' ';
            cout << endl;
            For(i, 1, n) cout <<ch[i][0] << ' ' << ch[i][1] << endl;*/
        }
    }

    return ;
}