欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

洛谷P3722 [AH2017/HNOI2017]影魔(线段树 set spaly)

程序员文章站 2022-12-15 08:58:49
题意 "题目链接" Sol 这题好毒瘤啊。。 首先要观察到几个性质: 1. 将最小值旋转到根相当于把右子树变为祖先的左子树,然后将原来的根变为当前最小值 2. 上述操作对深度的影响相当于右子树不变,其他的位置 1 然后就可以做了,把询问离线之后离散化一下,建一棵权值线段树表示每个值对应的深度 同时用 ......

题意

题目链接

sol

这题好毒瘤啊。。

首先要观察到几个性质:

  1. 将最小值旋转到根相当于把右子树变为祖先的左子树,然后将原来的根变为当前最小值

  2. 上述操作对深度的影响相当于右子树不变,其他的位置-1

然后就可以做了,把询问离线之后离散化一下,建一棵权值线段树表示每个值对应的深度

同时用set维护出已经加入的值

每次先找到后继,看一下有没有左孩子,如果有的话说明前驱一定没有右孩子。

注意随时更新信息

复杂度\(o(nlogn)\)

#include<bits/stdc++.h> 
#define pair pair<ll, ll>
#define mp(x, y) make_pair(x, y)
#define fi first
#define se second
#define ll long long 
#define fin(x) {freopen(#x".in","r",stdin);}
#define fout(x) {freopen(#x".out","w",stdout);}
using namespace std;
const int maxn = 1e6 + 10, mod = 1e9 + 7, inf = 1e9 + 10;
inline int read() {
    char c = getchar(); int x = 0, f = 1;
    while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * f;
}
int n, m, opt[maxn], val[maxn], date[maxn], cnt;
void des() {
    sort(date + 1, date + cnt + 1);
    cnt = unique(date + 1, date + cnt + 1) - date - 1;
    for(int i = 1; i <= m; i++) if(opt[i] == 1) val[i] = lower_bound(date + 1, date + cnt + 1, val[i]) - date;
}
set<int> s;
#define ls k << 1
#define rs k << 1 | 1
int add[maxn], root, f[maxn], ll[maxn], rr[maxn];
void ps(int k, int v) {
    add[k] += (rr[k] - ll[k] + 1) * v;
    f[k] += v;
}
void pushdown(int k) {
    if(!f[k]) return ;
    ps(ls, f[k]); ps(rs, f[k]);
    f[k] = 0;
}
void update(int k) {
    add[k] = add[ls] + add[rs];
}
void build(int k, int ll, int rr) {
    if(ll == rr) return ;
    int mid = ll + rr >> 1;
    build(ls, ll, mid); build(rs, mid + 1, rr);
}
void intadd(int k, int l, int r, int ql, int qr, int v) {
    if(ql <= l && r <= qr) {ps(k, v); return ;}
    pushdown(k);
    int mid = l + r >> 1;
    if(ql <= mid) intadd(ls, l, mid, ql, qr, v);
    if(qr  > mid) intadd(rs, mid + 1, r, ql, qr, v);
    update(k);
}
void modify(int k, int l, int r, int p, int v) {
    if(l == r) {add[k] = v; return ;}
    int mid = l + r >> 1;
    pushdown(k);
    if(p <= mid) modify(ls, l, mid, p, v);
    else modify(rs, mid + 1, r, p, v);
    update(k);
}
int query(int k, int l, int r, int p) {
    if(l == r) return add[k];
    int mid = l + r >> 1;
    pushdown(k);
    if(p <= mid) return query(ls, l, mid, p);
    else return query(rs, mid + 1, r, p);
}

#undef ls
#undef rs

#define ls(x) ch[x][0]
#define rs(x) ch[x][1]
int ch[maxn][2], fa[maxn];
void connect(int x, int _fa, int tag) {
    if(x == _fa || (_fa == m + 1)) return ;
    ch[_fa][tag] = x;
    fa[x] = _fa;
}
int insert(int v) {
    if(s.empty()) {root = v; modify(1, 1, m, v, 1); s.insert(v); fa[v] = m + 1; return 1;}
    auto nxt = s.upper_bound(v);
    if(nxt != s.end() && !ls(*nxt)) {
        int pos = *nxt;
        modify(1, 1, m, v, query(1, 1, m, pos) + 1);
        connect(v, pos, 0);
    } else {
        nxt--; int pos = *nxt;
        modify(1, 1, m, v, query(1, 1, m, pos) + 1);
        connect(v, pos, 1);
    }
    s.insert(v);
    return query(1, 1, m, v);
}
int rotatemin() {
    int mn = *s.begin(), v = query(1, 1, m, mn);
    intadd(1, 1, m, mn + 1, fa[mn] - 1, -1);
    intadd(1, 1, m, 1, m, 1);
    modify(1, 1, m, mn, 1); 
    connect(rs(mn), fa[mn], 0); 
    connect(root, mn, 1);
    root = mn; fa[root] = m + 1;
    return v;
}
int rotatemax() {
    auto it = s.end(); it--; 
    int mx = *it, v = query(1, 1, m, mx);
    intadd(1, 1, m, (fa[mx] == m + 1) ? 1 : fa[mx] + 1, mx - 1, -1);
    intadd(1, 1, m, 1, m, 1);
    modify(1, 1, m,  mx, 1); 
    connect(ls(mx), fa[mx], 1);
    connect(root, mx, 0);
    root = mx; fa[root] = m + 1;
    return v;
}
int deletmin() {
    int v = rotatemin(); 
    int mn = *s.begin();  fa[rs(mn)] = m + 1;  root = rs(mn);
    intadd(1, 1, m, 1, m, -1);
    modify(1, 1, m, mn, 0);
    fa[mn] = rs(mn) = ls(mn) = 0; 
    s.erase(mn);
    return v;
}
int deletmax() {
    int v = rotatemax();
    auto it = s.end(); it--;
    int mx = *it;  fa[ls(mx)] = m + 1; root = ls(mx);
    intadd(1, 1, m, 1, m, -1);
    modify(1, 1, m, mx, 0); 
    fa[mx] = ls(mx) = rs(mx) = 0;
    s.erase(mx);
    return v;
}
signed main() {
    m = read();
    for(int i = 1; i <= m; i++) {
        opt[i] = read(); 
        if(opt[i] == 1) val[i] = read(), date[++cnt] = val[i];
    }
    build(1, 1, m);
    des();
    for(int i = 1; i <= m; i++) {
        if(opt[i] == 1) printf("%d\n", insert(val[i]));
        else if(opt[i] == 2) printf("%d\n", rotatemin());
        else if(opt[i] == 3) printf("%d\n", rotatemax());
        else if(opt[i] == 4) printf("%d\n", deletmin());
        else printf("%d\n", deletmax());
    }
    return 0;
}
/*
4
1 39877
1 76497
2
1 6377
*/