[luogu1110]:[ZJOI2007]报表统计

[luogu1110]:[ZJOI2007]报表统计

题目链接

我就是魔法的化身


Solution

维护一个 FHQtreap 和一个 multiset
我们考虑第一个操作实际上就是待修改的小跟堆
第二个操作平衡树上维护前驱后继,然后插入即可

dhy太神了,天天过来给我施加压力…蒟蒻调个代码容易吗..


Code

#include<cstdio>
#include<cstring>
#include<cctype>
#include<ctime>
#include<cmath>
#include<set>
#include<algorithm>

using namespace std;

inline int read() {
    char c = getchar(); int x = 0, f = 1;
    while(!isdigit(c)) {if(c == '-') f = -1; c = getchar();}
    do {x = x * 10 + (c ^ 48); c = getchar();} while(isdigit(c));
    return x * f;
}

const int N = 5e5 + 29;
const int inf = 2e9;
int nxt[N], a[N];
struct Node {
    int siz, val, rnd;
    Node *ch[2];
    void maintain() {
        siz = ch[0]->siz + ch[1]->siz + 1;
    }
} pool[N << 1], *root, *null, *rt1, *rt2, *rt3;
int mingap, minsortgap;
char c[233];
multiset<int> s;

void init() {
    null = &pool[0];
    null->siz = null->val = null->rnd = 0;
    null->ch[0] = null->ch[1] = NULL;
    root = null;
    mingap = inf;
    minsortgap = inf;
}

Node *newNode(int v) {
    static int cnt = 1;
    pool[cnt].siz = 1; pool[cnt].val = v; pool[cnt].rnd = rand();
    pool[cnt].ch[0] = pool[cnt].ch[1] = null;
    return &pool[cnt++];
}

void split(Node *o, int k, Node *&x, Node *&y) {
    if(o == null) x = y = null;
    else {
        if(o->val <= k) {
            x = o; split(o->ch[1], k, o->ch[1], y);
        } else {
            y = o; split(o->ch[0], k, x, o->ch[0]);
        }
        o->maintain();
    }
}

Node *merge(Node *x, Node *y) {
    if(x == null) return y;
    if(y == null) return x;
    if(x->rnd < y->rnd) {
        x->ch[1] = merge(x->ch[1], y);
        x->maintain(); return x;
    } else {
        y->ch[0] = merge(x, y->ch[0]);
        y->maintain(); return y;
    }
}

Node *kth(Node *o, int k) {
    if(k <= o->ch[0]->siz) return kth(o->ch[0], k);
    if(k == o->ch[0]->siz + 1) return o;
    return kth(o->ch[1], k - 1 - o->ch[0]->siz);
}

int main() {
    //freopen("make.in", "r", stdin);
    //freopen("debug.out", "w", stdout);
    init();
    int n = read(), m = read();
    for(int i = 1; i <= n; ++i) {
        a[i] = read();
        nxt[i] = a[i];
        if(i != 1) {
            int delta = abs(a[i] - a[i - 1]);
            s.insert(delta);
        }
        split(root, a[i] - 1, rt1, rt2);
        if(rt1 != null) minsortgap = min(minsortgap, a[i] - kth(rt1, rt1->siz)->val);
        split(rt2, a[i], rt2, rt3);
        if(rt3 != null) minsortgap = min(minsortgap, kth(rt3, 1)->val - a[i]);
        if(rt2 != null) minsortgap = 0;
        rt2 = merge(rt2, newNode(a[i]));
        rt2 = merge(rt2, rt3);
        root = merge(rt1, rt2);
    }
    while(m--) {
        scanf("%s", c + 1);
        if(c[1] == 'I') {
            int x = read(), y = read(); // nxt[x], y, a[x + 1]

            s.insert(abs(y - nxt[x]));
            if(x != n) {
                s.insert(abs(a[x + 1] - y)); 
                int tmp = abs(a[x + 1] - nxt[x]);
                s.erase(s.find(tmp));
            }   

            split(root, y - 1, rt1, rt2);
            if(rt1 != null) minsortgap = min(minsortgap, y - kth(rt1, rt1->siz)->val);
            split(rt2, y, rt2, rt3);
            if(rt3 != null) minsortgap = min(minsortgap, kth(rt3, 1)->val - y);
            if(rt2 != null) minsortgap = 0;
            rt2 = merge(rt2, newNode(y));
            rt2 = merge(rt2, rt3);
            root = merge(rt1, rt2);

            nxt[x] = y;
        } else {
            if(c[5] == 'S') {
                printf("%d\n", minsortgap);
            } else {
                int ans = *s.begin();
                printf("%d\n", ans);
            }
        }
    }
    return 0;
}

/*
3 5
5 3 1
MIN_GAP
MIN_SORT_GAP

INSERT 2 9

INSERT 2 6
MIN_SORT_GAP


3 5
5 3 1
INSERT 2 9
MIN_SORT_GAP
INSERT 2 6
MIN_GAP
MIN_SORT_GAP

10 10
28284 10829 22689 11134 20423 10495 13585 19418 4080 15884 
INSERT 7 5789
MIN_GAP
MIN_SORT_GAP
INSERT 4 19393
MIN_GAP
MIN_SORT_GAP
INSERT 6 680
MIN_GAP
MIN_SORT_GAP
INSERT 5 4903


*/

1
说点什么

avatar
1 Comment threads
0 Thread replies
1 Followers
 
Most reacted comment
Hottest comment thread
1 Comment authors
DefFrancis Recent comment authors
  Subscribe  
最新 最旧 得票最多
提醒
DefFrancis
游客
DefFrancis

又被可爱的mxgDiss了