• https://www.luogu.com.cn/problem/P3765

线段树维护潜在众数。
平衡树再进行核对。
我们可以用 atl 里的线段树，平板电视里的平衡树。
四舍五入等于啥都不用写。

#include <lastweapon/io>
#include <lastweapon/segtree>
#include <ext/pb_ds/assoc_container.hpp>
using namespace lastweapon;
using namespace __gnu_pbds;

const int N = int(5e5) + 9;

PII op(PII a, PII b) {
    if(a.fi == b.fi) return {a.fi, a.se+b.se};
    if(a.se >= b.se) return {a.fi, a.se-b.se};
    return {b.fi, b.se-a.se};
}

PII e() {
    return {0, 0};
}

tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> T[N];

int main() {
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
#endif

    int n,m; RD(n,m);
    vector<PII> a(n);
    REP(i, n) {
        T[RD(a[i].fi)].insert(i);
        a[i].se = 1;
    }

    segtree<PII, op, e> S(a);
    DO(m) {
        int l,r,s; RD(l,r,s); --l; int x = S.prod(l, r).fi;
        if(T[x].order_of_key(r)-T[x].order_of_key(l)>(r-l)/2) s = x;
        Rush {
            S.set(--RD(x), {s, 1});
            if (a[x].fi != s) {
                T[a[x].fi].erase(x); ;
                T[a[x].fi = s].insert(x);
            }
        }
        OT(s);
    }
    int x = S.prod(0, n).fi;
    OT(SZ(T[x]) > n/2 ? x :-1);
}

Posted by xiaodao
Category: 日常