Zhengxi Liu's Blog

// P3765 总统选举
#include<bits/stdc++.h>
using namespace std;

const int N = 5e5 + 7, INF = 1e9;

int n, q, x, y, s, K, tot, id, cnt, val;

struct splay_tree{

    #define kl T[k].son[0]
    #define kr T[k].son[1]

    int rt[N];

    struct node{
        int son[2], fa, idx, sz, col;
        void init(int p, int id, int c){
            fa = p, idx = id, sz = 1, col = c;
        }
    }T[N * 10];

    void push_up(int k){
        T[k].sz = T[kl].sz + T[kr].sz + 1;
    }

    void rotate(int k){
        int p = T[k].fa, gp = T[p].fa;
        bool op = T[p].son[1] == k;
        T[gp].son[T[gp].son[1] == p] = k;
        T[k].fa = gp;
        T[p].son[op] = T[k].son[op ^ 1];
        T[T[k].son[op ^ 1]].fa = p;
        T[k].son[op ^ 1] = p;
        T[p].fa = k;
        push_up(p), push_up(k);
    }

    void splay(int k, int lim){
        while(T[k].fa != lim){
            int p = T[k].fa, gp = T[p].fa;
            if(gp != lim){
                if(T[p].son[1] == k ^ T[gp].son[1] == p) rotate(k);
                else rotate(p);
            }
            rotate(k);
        }
        if(!lim) rt[T[k].col] = k;
    }
    
    void build(){
        for(int i = 1; i <= n; i ++){
            rt[i] = ++ tot;
            T[tot].init(0, -INF, i);
            T[tot].son[1] = tot + 1;
            ++ tot;
            T[tot].init(tot - 1, INF, i);
            splay(tot, 0);
        }
    }

    int find(int pos, int col){
        int k = rt[col];
        while(T[k].idx != pos && T[k].son[T[k].idx < pos])
            k = T[k].son[T[k].idx < pos];
        splay(k, 0);
        return k;
    }

    int pre(int pos, int col){
        int k = find(pos, col);
        if(T[k].idx < pos) return k;
        k = kl;
        while(kr) k = kr;
        splay(k, 0);
        return k;
    }

    int suc(int pos, int col){
        int k = find(pos, col);
        if(T[k].idx > pos) return k;
        k = kr;
        while(kl) k = kl;
        splay(k, 0);
        return k;
    }

    void del(int pos, int col){
        int ll = pre(pos, col), rr = suc(pos, col);
        splay(ll, 0), splay(rr, ll);
        T[rr].son[0] = 0, splay(rr, 0);
    }

    void insert(int pos, int col){
        int ll = pre(pos, col), rr = suc(pos, col);
        splay(ll, 0), splay(rr, ll);
        T[++ tot].init(rr, pos, col);
        T[rr].son[0] = tot, splay(rr, 0);
    }

    int qry(int ll, int rr, int col){
        int xx = pre(ll, col), yy = suc(rr, col);
        splay(xx, 0), splay(yy, xx);
        return T[T[yy].son[0]].sz;
    }

    #undef kl
    #undef kr

}spl;

struct seg_tree{

    #define kl (k << 1)
    #define kr ((k << 1) | 1)
    #define mid ((l + r) >> 1)

    struct node{
        int num, cnt;
    }T[N << 2];

    node push_up(node ll, node rr){
        if(ll.num == -1) return rr;
        node res;
        if(ll.num == rr.num) res = {ll.num, ll.cnt + rr.cnt};
        else {
            if(ll.cnt >= rr.cnt) res = {ll.num, ll.cnt - rr.cnt};
            else res = {rr.num, rr.cnt - ll.cnt};
        }
        return res;
    }

    void upd(int k, int l, int r, int pos, int v){
        if(l == r){
            T[k] = {v, 1};
            return;
        }
        if(mid >= pos) upd(kl, l, mid, pos, v);
        else upd(kr, mid + 1, r, pos, v);
        T[k] = push_up(T[kl], T[kr]);
    }

    node qry(int k, int l, int r, int x, int y){
        if(l >= x && r <= y) return T[k];
        node res = {-1, -1};
        if(mid >= x) res = qry(kl, l, mid, x, y);
        if(mid < y) res = push_up(res, qry(kr, mid + 1, r, x, y));
        return res;
    }

    #undef kl
    #undef kr
    #undef mid

}seg;

int to[N];

int main(){

    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> q;

    spl.build();

    for(int i = 1; i <= n; i ++){
        cin >> to[i];
        spl.insert(i, to[i]);
        seg.upd(1, 1, n, i, to[i]);
    }

    while(q --){

        cin >> x >> y >> s >> K;

        int win = seg.qry(1, 1, n, x, y).num, len = y - x + 1;
        if(spl.qry(x, y, win) < len / 2 + 1) win = s;
        while(K --){
            cin >> id;
            spl.del(id, to[id]);
            spl.insert(id, win);
            seg.upd(1, 1, n, id, win);
            to[id] = win;
        }

        cout << win << endl;

    }

    int win = seg.qry(1, 1, n, 1, n).num;
    if(spl.qry(1, n, win) < n / 2 + 1) win = -1;
    cout << win << endl;

    return 0;
}

#include<bits/stdc++.h>
using namespace std;

#define ls(x) T[x].son[0]
#define rs(x) T[x].son[1]
#define fa(x) T[x].p
#define not_rt(x) ls(fa(x)) == x || rs(fa(x)) == x

const int N = 1e5 + 7;

struct node{
    int son[2], p, sum, v;
    bool tag;
}T[N];

int n, m, op, x, y;

void push_up(int k){
    T[k].sum = T[ls(k)].sum ^ T[rs(k)].sum ^ T[k].v;
}

void push_down(int k){
    if(!T[k].tag) return;
    swap(ls(k), rs(k));
    T[ls(k)].tag ^= 1;
    T[rs(k)].tag ^= 1;
    T[k].tag = 0;
}

void rotate(int k){
    int p = fa(k), gp = fa(p);
    bool op = rs(p) == k;
    if(not_rt(p)) T[gp].son[rs(gp) == p] = k; // virtual father cannot point to son
    fa(k) = gp, fa(p) = k;
    T[p].son[op] = T[k].son[op ^ 1];
    fa(T[k].son[op ^ 1]) = p;
    T[k].son[op ^ 1] = p;
    push_up(p), push_up(k);
}

void push_all(int k){
    if(not_rt(k)) push_all(fa(k));
    push_down(k);
}

void splay(int k){
    push_all(k); // son left/right order must be correct in order to splay correctly
    while(not_rt(k)){
        int p = fa(k), gp = fa(p);
        if(not_rt(p)){
            if(ls(p) == k ^ ls(gp) == p) rotate(k);
            else rotate(p);
        }
        rotate(k);
    }
}

void access(int k){ // establish real edge all the way to root
    for(int y = 0; k; ){
        splay(k); // move current node to the root of the current splay tree
        rs(k) = y;
        // Two moves in one:
        // 1. unbind the real edge that used to be at rs, so there are no nodes with depth greater than the initial k
        // 2. connect the other previous nodes that is above the initial k to this node
        push_up(k);
        y = k, k = fa(k);
    }
}

void make_rt(int k){
    access(k);
    splay(k);
    T[k].tag ^= 1;
    // the node k is moved to the root, but in the in-order travesal, it is still the deepest node
    // thus, we need to mandatorily reorder the tree, so that the deepest node is shallowest, and vice versa
    // (all the nodes left of k is shallower than k, right is deeper)
}

void split(int x, int y){
    make_rt(x); // make x the root of every node
    access(y); // let x and y be in the same splay tree
    splay(y); // prevent possible tle
}

int find_rt(int k){
    access(k);
    splay(k);
    while(ls(k)) // must include push_down!!!
        push_down(k), k = ls(k);
    splay(k);
    return k;
}

void link(int x, int y){
    make_rt(x);
    if(find_rt(y) != x) fa(x) = y;
}

void cut(int x, int y){
    make_rt(x);
    if(find_rt(y) == x && fa(y) == x && !ls(y)){
        // !ls(y) means there are no nodes that are stuck between the depth of x and y
        rs(x) = fa(y) = 0;
        push_up(x);
    }
}

int main(){

    cin >> n >> m;

    for(int i = 1; i <= n; i ++){
        cin >> x;
        T[i].v = T[i].sum = x;
    }

    while(m --){

        cin >> op >> x >> y;

        if(!op) split(x, y), cout << T[y].sum << endl;
        if(op == 1) link(x, y);
        if(op == 2) cut(x, y);
        if(op == 3) splay(x), T[x].v = y, push_up(x); // must push_up!!!

    }

    return 0;
}