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;
}