「Luogu 3765」总统选举 (线段树 + Splay, 摩尔投票法求区间大于一半数的众数)

发表于 | | + s

Luogu 3765
题意：维护序列的区间大于一半数的众数，带修。

第一眼以为带修主席树，感觉肯定跑不过

前置知识：Luogu 2397

求序列大于一半数的众数

本题可以采用摩尔投票法求，即将不同数两两消除，最后一定剩下的是这个众数。
这个方法必须存在大于一半数的众数

然后看这题，显然摩尔投票法是满足可加性的，那么线段树维护之。

但是如果不满足存在大于一半数的众数怎么办？

我们可以维护一个数在某个区间出现次数，这个方法是经典套路，静态则用 vector 排序后二分，而动态则需要名次树Splay维护。具体方法为在名次树上类似静态方法二分即可。

然后每次查询，更改即可。

知识点：
1、摩尔投票法
2、vector 版平衡树

#include<cstdio> 
#include<cstring>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<set>
#include<vector>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
#define fir first
#define sec second
#define mp make_pair
using namespace std;

namespace flyinthesky {

    const int MAXN = 500000 + 5, INF = 2000000000;

    int n, m, vt[MAXN];
    struct qwq {
        vector<int > a;
        void insert(int x) {a.insert(lower_bound(a.begin(), a.end(), x), x);}
        void del(int x) {a.erase(lower_bound(a.begin(), a.end(), x));}
        int rank(int x) {return lower_bound(a.begin(), a.end(), x) - a.begin() + 1;}
        int kth(int k) {return a[k - 1];}
        int pre(int x) {return a[lower_bound(a.begin(), a.end(), x) - a.begin() - 1];}
        int succ(int x) {return a[upper_bound(a.begin(), a.end(), x) - a.begin()];}
    }s[MAXN];

    int chk(int l, int r, int i) { // 1
        if (i == 0) return 0;
        return upper_bound(s[i].a.begin(), s[i].a.end(), r) - upper_bound(s[i].a.begin(), s[i].a.end(), l - 1);
    }

    #define lc (o << 1)
    #define rc (o << 1 | 1)
    #define M ((l + r) >> 1)
    #define lson lc, l, M
    #define rson rc, M + 1, r 
    int cnt[MAXN * 4], num[MAXN * 4];
    void pushup(int o) { // 1
        if (num[lc] == num[rc]) num[o] = num[lc], cnt[o] = cnt[lc] + cnt[rc];
        else {
            if (cnt[lc] > cnt[rc]) cnt[o] = cnt[lc] - cnt[rc], num[o] = num[lc];
            else cnt[o] = cnt[rc] - cnt[lc], num[o] = num[rc];
        }
    }
    void build(int o, int l, int r) { // 1
        cnt[o] = num[o] = 0;
        if (l == r) return ; else {
            build(lson), build(rson);
            pushup(o);
        }
    }
    int query(int o, int l, int r, int x, int y, int &whw) {
        if (x <= l && r <= y) { // 1
            return whw = cnt[o], num[o];
        }
        int ret = 0, cc = 0;
        if (x <= M) {
            ret = query(lson, x, y, cc);
        }
        if (M < y) {
            int tmp1, tmp2;
            tmp1 = query(rson, x, y, tmp2);
            if (tmp1 == ret) cc += tmp2; else {
                if (tmp2 > cc) ret = tmp1, cc = tmp2 - cc; 
                else cc = cc - tmp2;
            }
        }
        return whw = cc, ret;
    }
    void update(int o, int l, int r, int p, int v) { // 1
        if (l == r) {
            cnt[o] = 1, num[o] = v;
            return ;
        }
        if (p <= M) update(lson, p, v);
        else update(rson, p, v);
        pushup(o);
    }

    void clean() {
    }
    int solve() {

        clean();

        cin >> n >> m;
        build(1, 1, n);

        for (int i = 1; i <= n; ++i) 
            scanf("%d", &vt[i]), 
            update(1, 1, n, i, vt[i]), s[vt[i]].insert(i), s[i].insert(INF), s[i].insert(-INF);

        while (m--) {
            int l, r, si, k; scanf("%d%d%d%d", &l ,&r, &si, &k);
            int gg, ret = query(1, 1, n, l, r, gg);
            if (chk(l, r, ret) <= (r - l + 1) / 2) printf("%d\n", ret = si); else printf("%d\n", ret);
            for (int x, i = 1; i <= k; ++i) {
                scanf("%d", &x);
                update(1, 1, n, x, ret);
                s[vt[x]].del(x), s[vt[x] = ret].insert(x);
            }
        }

        int gg, ret = query(1, 1, n, 1, n, gg);
        if (chk(1, n, ret) <= (n - 1 + 1) / 2) printf("-1\n"); else printf("%d\n", ret);

        return 0;
    }
}
int main() {
    flyinthesky::solve();
    return 0;
}
/*
3 1000
1 2 3
2 3 0 0

5 400
1 2 3 4 5
1 2 1 1 3
5 5 1 2 2 4
2 4 0 0

5 400
1 5 1 5 5
2 4 0 0
*/
------ 本文结束 ------