20251123 LiveDream 平衡树

__JCY__ · 2025-11-23 16:11:10 · 个人记录

总结

期望: 100 + 100 + 0 = 200

实际: 100 + 100 + 0 = 200 rk2

T1 P1503 鬼子进村

考虑到对于一个兵能到哪些位置就是考虑前面一个被摧毁和后面一个被摧毁的位置，即前驱后继。即用平衡树维护，fhq 非常的好写。

::::info[code]

#include <bits/stdc++.h>
#define i64 long long

using namespace std;

const i64 kMaxN = 1e5 + 5;

struct E {
    struct Node {
        int v, ls, rs, sz, rk;
    } t[kMaxN];
    int tot, rt;

    void update(int x) {
        t[x].sz = t[t[x].ls].sz + t[t[x].rs].sz + 1;
    }
    int add(int val) {
        t[++tot] = Node{val, 0, 0, 1, rand()};
        return tot;
    }
    void split(int x, int& a, int& b, int val) {
        if (x == 0) {
            return a = b = 0, void();
        }
        if (t[x].v <= val) {
            a = x, split(t[x].rs, t[x].rs, b, val);
        } else {
            b = x, split(t[x].ls, a, t[x].ls, val);
        }
        update(x);
    }
    void merge(int &x, int a, int b) {
        if (a == 0 || b == 0) {
            return x = a + b, void();
        }
        if (t[a].rk > t[b].rk) {
            x = a, merge(t[a].rs, t[a].rs, b);
        } else {
            x = b, merge(t[b].ls, a, t[b].ls);
        }
        update(x);
    }
    void insert(int &x, int val) {
        int v = add(val), a = 0, b = 0;
        split(x, a, b, val);
        merge(a, a, v);
        merge(x, a, b);
    }
    void del(int &x, int val) {
        int a = 0, b = 0, c = 0;
        split(x, a, b, val);
        split(a, a, c, val - 1);
        merge(c, t[c].ls, t[c].rs);
        merge(a, a, c);
        merge(x, a, b);
    }
    int find(int x, int val) {
        for (; t[t[x].ls].sz + 1 != val; ) {
            if (t[t[x].ls].sz >= val) x = t[x].ls;
            else val -= t[t[x].ls].sz + 1, x = t[x].rs; 
        }
        return t[x].v;
    }
    int rnk(int &x, int val) {
        int a = 0, b = 0;
        split(x, a, b, val - 1);
        int v = t[a].sz + 1;
        merge(x, a, b);
        return v;
    }
    int prev(int &x, int val) {
        int a = 0, b = 0;
        split(x, a, b, val);
        int v = find(a, t[a].sz);
        merge(x, a, b);
        return v;
    }
    int suc(int &x, int val) {
        int a = 0, b = 0;
        split(x, a, b, val - 1);
        int v = find(b, 1);
        merge(x, a, b);
        return v;
    }
} t;

int st[kMaxN], tot, n, m;

signed main() {
    ios ::sync_with_stdio(0), cin.tie(0);
    srand(time(0));
    cin >> n >> m, t.rt = 0;
    t.insert(t.rt, 0), t.insert(t.rt, n + 1);
    for (int i = 1; i <= m; i++) {
        char c; cin >> c;
        if (c == 'D') {
            int x; cin >> x, st[++tot] = x;
            t.insert(t.rt, x);
        } else if (c == 'R') {
            int x = st[tot]; tot--;
            t.del(t.rt, x);
        } else {
            int x; cin >> x;
            int l = t.prev(t.rt, x), r = t.suc(t.rt, x);
            cout << (l == r ? 0 : r - l - 1) << '\n';
        }
    }
    return 0;
}

::::

T2 P2572 [SCOI2010] 序列操作

赛时想法：线段树平衡树方法：

维护按 size 劈的 fhq；
维护赋值标记 tag, 取反标记 rev；
维护 pushdown函数，先下传赋值标记，再下穿取反标记，清空；
在 split 与 merge 诋毁前要将标记下传；
维护前缀0/1，后缀0/1，最长0/1 与线段树同理；

::::info[赛时code]

#include <bits/stdc++.h>
#define ls(x) x << 1
#define rs(x) x << 1 | 1

using namespace std;

const int kMaxN = 1e5 + 5;

struct N {
    int cnt[2], maxl[2], maxr[2], mx[2], tg[2], len;
    N() {
        cnt[0] = cnt[1] = maxl[0] = maxr[0] = mx[0] = mx[1] = tg[1] = len = 0; 
        tg[0] = -1;
    }
} t[kMaxN << 2];

int a[kMaxN], n, m;

void add1(int x) { //反转 
    t[x].tg[1] ^= 1;
    swap(t[x].cnt[0], t[x].cnt[1]);
    swap(t[x].maxl[0], t[x].maxl[1]);
    swap(t[x].maxr[0], t[x].maxr[1]);
    swap(t[x].mx[0], t[x].mx[1]);
}

void add2(int x, int op) { //赋值 0 1 
    t[x].tg[0] = op, t[x].tg[1] = 0;
    t[x].cnt[op] = t[x].maxl[op] = t[x].maxr[op] = t[x].mx[op] = t[x].len;
    t[x].cnt[!op] = t[x].maxl[!op] = t[x].maxr[!op] = t[x].mx[!op] = 0;
}

N Mix(N A, N B) {
    N C;
    C.len = A.len + B.len;
    C.tg[0] = -1, C.tg[1] = 0;
    for (int i = 0; i <= 1; i++) {  
        C.cnt[i] = A.cnt[i] + B.cnt[i];
        C.mx[i] = max({A.mx[i], B.mx[i], A.maxr[i] + B.maxl[i]});
        C.maxl[i] = A.maxl[i];
        if (A.cnt[i] == A.len) C.maxl[i] = A.len + B.maxl[i];
        C.maxr[i] = B.maxr[i];
        if (B.cnt[i] == B.len) C.maxr[i] = B.len + A.maxr[i]; 
    }
    return C;
}

void pushup(int x) {
    t[x] = Mix(t[ls(x)], t[rs(x)]); 
}

void pushdown(int x) {
    if (t[x].tg[0] != -1) {
        add2(ls(x), t[x].tg[0]);
        add2(rs(x), t[x].tg[0]);
        t[x].tg[0] = -1;
    }
    if (t[x].tg[1]) {
        add1(ls(x));
        add1(rs(x));
        t[x].tg[1] = 0;
    }
}

void build(int x, int l, int r) {
    if (l == r) {
        t[x].cnt[a[l]] = t[x].maxl[a[l]] = t[x].maxr[a[l]] = t[x].mx[a[l]] = t[x].len = 1;
        t[x].tg[0] = -1, t[x].tg[1] = 0;
        return;
    }
    int mid = l + r >> 1;
    build(ls(x), l, mid);
    build(rs(x), mid + 1, r);
    pushup(x);
}

void update(int x, int l, int r, int L, int R, int op) {
    if (L <= l && r <= R) {
        if (op == 0 || op == 1) add2(x, op);
        else add1(x);
        return;
    }
    int mid = l + r >> 1;
    pushdown(x);
    if (L <= mid) update(ls(x), l, mid, L, R, op);
    if (mid < R) update(rs(x), mid + 1, r, L, R, op); 
    pushup(x);
} 

N query(int x, int l, int r, int L, int R) {
    if (L <= l && r <= R) {
        return t[x];
    }
    pushdown(x);
    int mid = l + r >> 1, f1 = (L <= mid), f2 = (mid < R);
    if (f1 && !f2) return query(ls(x), l, mid, L, R);
    if (!f1 && f2) return query(rs(x), mid + 1, r, L, R);
    if (f1 && f2) return Mix(query(ls(x), l, mid, L, R), query(rs(x), mid + 1, r, L, R));
    return N();
}

signed main() {
    ios:: sync_with_stdio(0), cin.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    build(1, 1, n);
    for (int i = 1; i <= m; i++) {
        int op, l, r; cin >> op >> l >> r, l++, r++;
        if (op <= 2) update(1, 1, n, l, r, op);
        else if (op == 3) cout << query(1, 1, n, l, r).cnt[1] << '\n';
        else cout << query(1, 1, n, l, r).mx[1] << '\n';
    }
    return 0;
}

::::

T3 [APIO2015] 巴邻旁之桥

若一个人的两点在同一边，则不需要决策，可以直接算答案
- 情况1：k = 1
- 设位置为 p, 则第 i 个人的通勤距离为 \left | s_i - p \right | + 1 + \left | T_i - p \right | ，其中 cnt 表示再河的两边的人数；
- 问题转换为 2 \times cnt，寻找一个位置 p，是的所有点到 p 的距离最小。即中位数；

情况2：k = 2
设桥的位置为 p, q，当 s_i, t_i 中间有桥时，贡献为 \left | s_i - t_i \right | + 1；
当 p \le s_i \le t_i \le q，则 s_i - p \le q - Ti 时，会去 p 桥，否则去 q 桥。移项 s_i + t_i \le p + q 时，选 p 桥；
当 p q 确定是，按 s_i + t_i 排序，选 p 的一定时排序的一段前缀；
对于 cnt 个人，枚举分解先，左侧的人去 p，右侧的人去 q。即转化为情况1；
维护两个平衡树，分别存前后点的位置，动态删除与插入，找中位数即可；

::::info[code]

#include <bits/stdc++.h>
#define i64 long long
#define int long long

using namespace std;

const i64 kMaxN = 5e5 + 5, INF = 1e18;

struct E {
    struct Node {
        int v, ls, rs, sz, rk, sum;
    } t[kMaxN];
    int tot, rt;

    void update(int x) {
        t[x].sz = t[t[x].ls].sz + t[t[x].rs].sz + 1;
        t[x].sum = t[t[x].ls].sum + t[t[x].rs].sum + t[x].v;
    }
    int add(int val) {
        t[++tot] = Node{val, 0, 0, 1, rand(), val};
        return tot;
    }
    void split(int x, int& a, int& b, int val) {
        if (x == 0) {
            return a = b = 0, void();
        }
        if (t[x].v <= val) {
            a = x, split(t[x].rs, t[x].rs, b, val);
        } else {
            b = x, split(t[x].ls, a, t[x].ls, val);
        }
        update(x);
    }
    void merge(int &x, int a, int b) {
        if (a == 0 || b == 0) {
            return x = a + b, void();
        }
        if (t[a].rk > t[b].rk) {
            x = a, merge(t[a].rs, t[a].rs, b);
        } else {
            x = b, merge(t[b].ls, a, t[b].ls);
        }
        update(x);
    }
    void insert(int &x, int val) {
        int v = add(val), a = 0, b = 0;
        split(x, a, b, val);
        merge(a, a, v);
        merge(x, a, b);
    }
    void del(int &x, int val) {
        int a = 0, b = 0, c = 0;
        split(x, a, b, val);
        split(a, a, c, val - 1);
        merge(c, t[c].ls, t[c].rs);
        merge(a, a, c);
        merge(x, a, b);
    }
    int find(int x, int val) {
//      assert(val != 0);
        if (val == 0) return 0;
        for (; t[t[x].ls].sz + 1 != val; ) {
            if (t[t[x].ls].sz >= val) x = t[x].ls;
            else val -= t[t[x].ls].sz + 1, x = t[x].rs; 
        }
        return t[x].v;
    }
    int sum(int &x, int val, int ret = 0) {
        int a = 0, b = 0;
        split(x, a, b, val);
        ret -= t[a].sum - t[a].sz * val;
        ret -= t[b].sz * val - t[b].sum;
        merge(x, a, b);
        return ret;
    }
} t1, t2;

int s[kMaxN], t[kMaxN], a[kMaxN], tot, n, k, ans;

bool cmp(int x, int y) {
    return s[x] + t[x] < s[y] + t[y];
}

signed main() {
    ios ::sync_with_stdio(0), cin.tie(0);
    srand(time(0));
    cin >> k >> n;
    for (int i = 1; i <= n; i++) {
        char op1, op2; int x, y;
        cin >> op1 >> x >> op2 >> y;
        if (op1 == op2) ans += abs(y - x);
        else {
            ++tot, ans++;
            s[tot] = x, t[tot] = y;
            a[tot] = tot;
        }
    }
    sort(a + 1, a + tot + 1, cmp);
    t1.rt = t2.rt = 0;
    for (int i = 1; i <= tot; i++) {
        t2.insert(t2.rt, s[a[i]]), t2.insert(t2.rt, t[a[i]]);
    }
    int r = INF;
    if (k == 1) {
        int p = t2.find(t2.rt, tot);
        r = t2.sum(t2.rt, p);
    } else {
        int p = t2.find(t2.rt, tot);
        r = t2.sum(t2.rt, p);
        for (int i = 1; i < tot; i++) {
            t2.del(t2.rt, s[a[i]]), t2.del(t2.rt, t[a[i]]);
            t1.insert(t1.rt, s[a[i]]), t1.insert(t1.rt, t[a[i]]);
            int p = (t1.find(t1.rt, i) + t1.find(t1.rt, i + 1)) / 2;
            int q = (t2.find(t2.rt, tot - i) + t2.find(t2.rt, tot - i + 1)) / 2;
            r = min(r, t1.sum(t1.rt, p) + t2.sum(t2.rt, q));

        }
    }
    cout << ans + r << '\n';
    return 0;
}

::::