fhq-treap#9TLE求调

Sherlock___Holmes @ 2022-10-09 17:14:05

#include <cstdio>
#include <cstdlib>
#include <tuple>
#define int long long
#define re register
#define get getchar()
inline int read(){
    re int x = 0 , f = 1;re char c = get;
    while (c < '0' || c > '9') f ^= !(c ^ 45) , c = get;
    while (c >= '0' && c <= '9') x = (x << 1) + (x << 3) + (c ^ 48) , c = get;
    return f ? x : -x;
}
struct Node{
    Node *ch[2];
    int val , prio , cnt , siz;
    Node (int val) : val(val) , cnt(1) , siz(1){
        ch[0] = ch[1] = nullptr;
        prio = rand();
    } Node (Node *_node){
        val = _node -> val , cnt = _node -> cnt , siz = _node -> siz , prio = _node -> prio;
    } inline void upd_siz(){
        siz = cnt;
        if (ch[0] != nullptr) siz += ch[0] -> siz;
        if (ch[1] != nullptr) siz += ch[1] -> siz;
    }
};
struct fhq_treap{
    Node *root;
    std::pair <Node * , Node *> split(Node *cur , re int key){
        if (cur == nullptr) return {nullptr , nullptr};
        if (cur -> val <= key){
            auto temp = split(cur -> ch[1] , key);
            cur -> ch[1] = temp.first;
            cur -> upd_siz();
            return {cur , temp.second};
        } else{
            auto temp = split(cur -> ch[0] , key);
            cur -> ch[0] = temp.second;
            cur -> upd_siz();
            return {temp.first , cur};
        }
    } std::tuple <Node * , Node * , Node *> split_by_rk(Node *cur , re int rk){
        if (cur == nullptr) return {nullptr , nullptr , nullptr};
        re int ls_size = (cur -> ch[0] == nullptr ? 0 : cur -> ch[0] -> siz);
        if (rk <= ls_size){
            Node *l , *mid , *r;
            std::tie(l , mid , r) = split_by_rk(cur -> ch[0] , rk);
            cur -> ch[0] = r;
            cur -> upd_siz();
            return {l , mid , cur};
        } else if (rk <= ls_size + cur -> cnt){
            Node *lt = cur -> ch[0];
            Node *rt = cur -> ch[1];
            cur -> ch[0] = cur -> ch[1] = nullptr;
            return {lt , cur , rt};
        } else{
            Node *l , *mid , *r;
            std::tie(l , mid , r) = split_by_rk(cur -> ch[1] , rk - ls_size - cur -> cnt);
            cur -> ch[1] = l;
            cur -> upd_siz();
            return {cur , mid , r};
        }
    } Node* merge(Node* u , Node* v){
        if (u == nullptr && v == nullptr) return nullptr;
        if (u == nullptr && v != nullptr) return v;
        if (u != nullptr && v == nullptr) return u;
        if (u -> prio < v -> prio){
            u -> ch[1] = merge(u -> ch[1] , v);
            u -> upd_siz();
            return u;
        } else{
            v -> ch[0] = merge(u , v -> ch[0]);
            v -> upd_siz();
            return v;
        }
    } inline void del(re int val){
        auto tmp = split(root , val);
        auto ltr = split(tmp.first , val - 1);
        if (ltr.second -> cnt > 1){
            -- ltr.second -> cnt;
            ltr.second -> upd_siz();
            ltr.first = merge(ltr.first , ltr.second);
        }
        else{
            if (tmp.first == ltr.second) tmp.first = nullptr;
            delete ltr.second;
            ltr.second = nullptr;
        }
        root = merge(ltr.first , tmp.second);
    } inline void insert(re int val){
        auto temp = split(root , val);
        auto l_tr = split(temp.first , val - 1);
        Node *new_node;
        if (l_tr.second == nullptr) new_node = new Node(val);
        else{
            ++ l_tr.second -> cnt;
            l_tr.second -> upd_siz();
        }
        Node *l_tr_combined = merge(l_tr.first , l_tr.second == nullptr ? new_node : l_tr.second);
        root = merge(l_tr_combined , temp.second);
    } inline int qval_by_rank(Node *cur , re int rk){
        Node *l , *mid , *r;
        std::tie(l , mid , r) = split_by_rk(cur , rk);
        re int ret = mid -> val;
        root = merge(merge(l , mid) , r);
        return ret;
    }
}tr;
const int MAXN = 1e6 + 1;
int a[MAXN] , b[MAXN] , c[MAXN];
signed main(){
    srand(199994954);
    re int n = read() , k = read();
    for (re int i = 1;i <= k;++ i){
        c[i] = read();
        tr.insert(c[i]);
    }
    a[1] = tr.qval_by_rank(tr.root , 1);
    b[1] = tr.qval_by_rank(tr.root , k);
    for (re int i = k + 1;i <= n;++ i){
        tr.del(c[i - k]);
        c[i] = read();
        tr.insert(c[i]);
        a[i - k + 1] = tr.qval_by_rank(tr.root , 1);
        b[i - k + 1] = tr.qval_by_rank(tr.root , k);
    }
    for (re int i = 1;i <= n - k + 1;++ i) printf("%d " , a[i]);
    putchar('\n');
    for (re int i = 1;i <= n - k + 1;++ i) printf("%d " , b[i]);
    return 0;
}

by Sherlock___Holmes @ 2022-10-09 17:20:54

数组版的被卡常了。。。

#include <cstdio>
#include <cstdlib>
#define re register
#define get getchar()
struct fhq_treap{
    int ls, rs;
    int val, rd;
    int size;
} a[1100000];
int cnt, root;
inline int read(){
    re int x = 0 , f = 1;re char c = get;
    while (c < '0' || c > '9') f ^= !(c ^ 45) , c = get;
    while (c >= '0' && c <= '9') x = (x << 1) + (x << 3) + (c ^ 48) , c = get;
    return f ? x : -x;
}
inline void update (re int tp){a[tp].size = a[a[tp].ls].size + a[a[tp].rs].size + 1;}
inline void split (re int tp , re int k , re int &x , re int &y){
    if (!tp) {x = y = 0;return ;}
    else if (a[tp].val <= k) x = tp , split (a[tp].rs , k , a[tp].rs, y); 
    else y = tp , split(a[tp].ls , k , x , a[tp].ls);
    update(tp);
}
inline int merge (re int x , re int y){
    if (!x || !y) return x | y;
    if (a[x].rd > a[y].rd){
        a[x].rs = merge(a[x].rs, y);
        update(x);
        return x;
    }
    else{
        a[y].ls = merge(x, a[y].ls);
        update(y);
        return y;
    }
}
inline int new_node(re int x){
    a[++cnt].size = 1;
    a[cnt].val = x;
    a[cnt].rd = rand();
    return cnt;
}
inline void join(re int x){
    re int _x , _y;
    split(root , x - 1 , _x , _y);
    root = merge(merge(_x , new_node(x)) , _y);
}
inline void del(re int x){
    re int _x , _y , _z;
    split(root , x , _x , _z);
    split(_x , x - 1 , _x , _y);
    _y = merge(a[_y].ls , a[_y].rs);
    root = merge(merge(_x , _y) , _z);
}
inline int val (re int x){
    re int r = root;
    while (1){
        if (a[a[r].ls].size + 1 == x) return a[r].val;
        else if (a[a[r].ls].size + 1 > x) r = a[r].ls;
        else x -= a[a[r].ls].size + 1 , r = a[r].rs;
    }
}
const int MAXN = 1e6 + 1;
int d[MAXN] , b[MAXN] , c[MAXN];
signed main(){
    srand(199854554);
    re const int n = read() , k = read();
    for (re int i = 1;i <= k;++ i){
        c[i] = read();
        join(c[i]);
    }
    d[1] = val(1);
    b[1] = val(k);
    for (re int i = k + 1;i <= n;++ i){
        del(c[i - k]);
        c[i] = read();
        join(c[i]);
        d[i - k + 1] = val(1);
        b[i - k + 1] = val(k);
    }
    for (re int i = 1;i <= n - k + 1;++ i) printf("%d " , d[i]);
    putchar('\n');
    for (re int i = 1;i <= n - k + 1;++ i) printf("%d " , b[i]);
    return 0;
}

by Usada_Pekora @ 2022-10-09 17:59:12

@Sherlock___Holmes fhq 太慢了。。。换一个平衡树说不定还能过。

by hhw_khw @ 2022-10-09 18:15:21

用multiset+o2水过去了，估计是因为fhq常数略大

by Sherlock___Holmes @ 2022-10-09 20:58:12

@Zyingyzzz 数组的那个#9是1.02s,这卡不过去我是真难受

by Usada_Pekora @ 2022-10-09 21:02:30

@Sherlock___Holmes loj 上有一种非常快速的插入、删除写法。

可以参考这位大佬的代码优化常数。

#include <cstdio>
#include <random>

const int buf_size = 1 << 16;
char in_buf[buf_size], out_buf[buf_size], *in_st, *in_ed, *out_pos = out_buf;

char readChar() {
    if (in_st == in_ed) {
        in_ed = (in_st = in_buf) + fread(in_buf, 1, buf_size, stdin);

        if (in_st == in_ed)
            return EOF;
    }

    return *in_st++;
}
void readInt(int &x) {
    bool neg = false;
    char c;

    while ((c = readChar()) < '0' || c > '9')
        if (c == '-')
            neg = true;

    for (x = 0; c >= '0' && c <= '9'; c = readChar())
        x = x * 10 + c - '0';

    if (neg)
        x = -x;
}
template <typename... Args>
void readInt(int &x, Args &... args) {
    readInt(x);
    readInt(args...);
}
void flush() {
    fwrite(out_buf, out_pos - out_buf, 1, stdout), out_pos = out_buf;
}
struct _flusher {
    ~_flusher() {
        flush();
    }
} __flusher;
void writeChar(int c) {
    *out_pos++ = c;

    if (out_pos == out_buf + buf_size)
        flush();
}
void writeInt(int x) {
    if (x < 0)
        writeChar('-'), x = -x;

    if (x > 9)
        writeInt(x / 10);

    writeChar(x % 10 + '0');
}
void print(int x) {
    writeInt(x), writeChar('\n');
}

std::mt19937 rng(123);

struct node {
    int key, size, weight;
    node *l, *r;
};
node *root;
void pushup(node *x) {
    x->size = (x->l ? x->l->size : 0) + (x->r ? x->r->size : 0) + 1;
}
node *merge(node *l, node *r) {
    if (!l)
        return r;

    if (!r)
        return l;

    if (l->weight < r->weight) {
        l->r = merge(l->r, r);
        pushup(l);
        return l;
    } else {
        r->l = merge(l, r->l);
        pushup(r);
        return r;
    }
}
void split(node *x, int v, node *&l, node *&r) {
    if (!x) {
        l = r = nullptr;
        return;
    }

    if (x->key <= v) {
        l = x;
        split(x->r, v, x->r, r);
    } else {
        r = x;
        split(x->l, v, l, x->l);
    }

    pushup(x);
}
void insert(node *&x, node *v) {
    if (!x || v->weight < x->weight) {
        split(x, v->key, v->l, v->r);
        pushup(x = v);
        return;
    }

    if (v->key <= x->key)
        insert(x->l, v);
    else
        insert(x->r, v);

    pushup(x);
}
void erase(node *&x, int v) {
    if (x->key == v) {
        node *tmp = merge(x->l, x->r);
        delete x;
        x = tmp;
        return;
    }

    if (v < x->key)
        erase(x->l, v);
    else
        erase(x->r, v);

    pushup(x);
}
int kth(int k) {
    node *x = root;

    for (;;) {
        int sz = x->l ? x->l->size : 0;

        if (k <= sz)
            x = x->l;
        else if (k == sz + 1)
            return x->key;
        else
            k -= sz + 1, x = x->r;
    }
}
int rank(int k) {
    node *x = root;
    int res = 0;

    while (x) {
        int sz = x->l ? x->l->size : 0;

        if (k > x->key)
            res += sz + 1, x = x->r;
        else
            x = x->l;
    }

    return res;
}
int pred(int k) {
    node *x = root;
    int res = -1;

    while (x) {
        if (x->key < k)
            res = x->key, x = x->r;
        else
            x = x->l;
    }

    return res;
}
int succ(int k) {
    node *x = root;
    int res = -1;

    while (x) {
        if (x->key > k)
            res = x->key, x = x->l;
        else
            x = x->r;
    }

    return res;
}

int main() {
    int n;
    readInt(n);

    for (int op, x; n--;) {
        readInt(op, x);

        if (op == 1) {
            insert(root, new node{x, 1, (int)rng(), nullptr, nullptr});
        } else if (op == 2) {
            erase(root, x);
        } else if (op == 4) {
            print(kth(x));
        } else if (op == 3) {
            print(rank(x) + 1);
        } else if (op == 5) {
            print(pred(x));
        } else {
            print(succ(x));
        }
    }

    return 0;
}

by Sherlock___Holmes @ 2022-10-10 07:17:50

@Zyingyzzz 感谢