Lxzyzby Lxzyzby

Luogu P1110 [ZJOI2007]报表统计

in FHQ Treap read (32) 文章转载请注明来源!

题目链接

我们可以把 $n$ 个数,看成 $n$ 个序列,我们只关心每个序列的第一个数是什么和最后一个数是什么,记第一个数为 $beg_i$ 最后一个数为 $ed_i$

我们可以建两棵平衡树,一颗维护每个数的值,一颗维护差值

$INSERT(i,k)$ 时

  1. 当 $i!=n$ 时,把 $abs(beg[i+1]-ed[i])$ 在差值平衡树中删除、把 $abs(k-beg[i+1])$ 加入差值平衡树
  2. 把 $abs(ed[i]-k)$ 插入差值平衡树

在数值平衡树里,每一次的插入都可以取其前驱和后继,更新答案,直接记录结果即可。

#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize(2)
#pragma GCC optimize(3,"Ofast","inline")
const int MAXN = 2e6;
const int Inf = 0x3f3f3f3f;
struct FHQ_Treap {
    int rnd[MAXN], lc[MAXN], rc[MAXN], siz[MAXN], val[MAXN];
    int cnt, root, ans;
    FHQ_Treap() {
        root = 0; cnt = 0; ans = Inf;
    }
    int newnode(int x) {
        val[++cnt] = x; lc[cnt] = rc[cnt] = 0; siz[cnt] = 1; rnd[cnt] = rand();
        return cnt;
    } 
    void PushUp(int rt) {
        siz[rt] = 1;
        if(lc[rt]) siz[rt] += siz[lc[rt]];
        if(rc[rt]) siz[rt] += siz[rc[rt]];
    }
    void split(int rt, int C, int &x, int &y) {
        if(!rt) return x = y = 0, void();
        if(val[rt] <= C) x = rt, split(rc[rt], C, rc[rt], y);
        else y = rt, split(lc[rt], C, x, lc[rt]);
        PushUp(rt); 
    }
    int merge(int x, int y) {
        if(!x || !y) return x + y;
        if(rnd[x] < rnd[y]) return rc[x] = merge(rc[x], y), PushUp(x), x;
        else return lc[y] = merge(x, lc[y]), PushUp(y), y;
    }
    int Max(int rt) {
        while(rc[rt]) rt = rc[rt]; 
        return val[rt];
    }
    int Min(int rt) {
        while(lc[rt]) rt = lc[rt];
        return val[rt];
    }
    void insert(int C) {
        int x, y;
        split(root, C-1, x, y);
        root = merge(merge(x, newnode(C)), y);
    }
    void insert2(int C) {
        int x, y;
        split(root, C-1, x, y);
        if(siz[x]) ans = min(ans, abs(C - Max(x)));
        if(siz[y]) ans = min(ans, abs(C - Min(y)));
        root = merge(merge(x, newnode(C)), y);
    }
    void erase(int C) {
        int x, y, z;
        split(root, C-1, x, z);
        split(z, C, y, z);
        y = merge(lc[y], rc[y]);
        root = merge(merge(x, y), z);
    }
    int kth(int k, int rt) {
        int pos = rt;
        while(true) {
            if(k <= siz[lc[pos]]) pos = lc[pos];
            else if(k <= siz[lc[pos]] + 1) return pos;
            else k -= siz[lc[pos]] + 1, pos = rc[pos];
        }
    }
}t1, t2;
int n, m, beg[MAXN], ed[MAXN];
void SubtaskInsert() {
    int pos, x; scanf("%d%d", &pos, &x);
    t2.insert2(x);
    t1.insert(abs(ed[pos] - x));
    if(pos != n) {
        t1.erase(abs(beg[pos+1] - ed[pos]));
        t1.insert(abs(beg[pos+1] - x));
    }
    ed[pos] = x;
}
void SubtaskGap() {
    printf("%d\n", t1.Min(t1.root));
}
void SubtaskMinSortGap() {
    printf("%d\n", t2.ans);
}
int main() {
    srand(time(0));
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i++) {
        int x; scanf("%d", &x); beg[i] = ed[i] = x;
        t2.insert2(x); 
    }
    for(int i = 2; i <= n; i++) 
        t1.insert(abs(beg[i] - ed[i-1]));
    for(int i = 1; i <= m; i++) {
        char opt[20]; scanf("%s", opt);
        if(opt[0] == 'I') SubtaskInsert();
        if(opt[4] == 'G') SubtaskGap();
        if(opt[4] == 'S') SubtaskMinSortGap();
    }
    return 0;
}

本文基于《署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0)》许可协议授权
文章链接:https://zby.xyz/index.php/archives/83/ (转载时请注明本文出处及文章链接)

FHQ Treap
发表新评论
博客已萌萌哒运行
© 2020 由 Typecho 强力驱动.Theme by YoDu
PREVIOUS NEXT
雷姆
拉姆