题解：AT_abc483_c [ABC483C] Second Choice Election

px_poxiao · 2026-11-10 12:19:57 · 题解

分享一个异于常人的做法。

首先我们不难发现，如果 k 退选，他的得票归零的同时，所有第一志愿是 k 的选民都会投给第二志愿。

不难想到维护投给每个第一候选为 k 的选民的第二候选，每当选到对应的 k 时，模拟即可，这样时间复杂度均摊下来是 O(m) 的。

那么怎么快速寻找得票最多的人呢？线段树！搞一颗维护得票数和对应的人的编号，单点改区间最大值的线段树即可。这样代码的总时间复杂度就是 O(n \log n + m)。

于是我们使用线段树解决了一道黄题！可喜可贺！

赛事纪录 link。

#include <iostream>
#include <vector>
using namespace std;
#define endl '\n'
#define int long long
int n, m;
struct qw
{
    int a, b;
}a[200010], tr[800010];
vector<int> diff[200010];
int cnt[200010];
#define lc p << 1
#define rc p << 1 | 1
qw check(qw x, qw y){
    if(x.a != y.a){
        if(x.a > y.a)
            return x;
        else
            return y;
    }
    else{
        if(x.b < y.b)
            return x;
        else
            return y;
    }
}
inline void pushup(int p){
    tr[p] = check(tr[lc], tr[rc]);
}
void build(int p, int l, int r){
    if(l == r){
        tr[p] = {cnt[l], l};
        return;
    }
    int mid = l + ((r - l) >> 1);
    build(lc, l, mid);
    build(rc, mid+1, r);
    pushup(p);
}
void change(int p, int l, int r, int x, int v){
    if(l == r){
        tr[p].a += v;
        return;
    }
    int mid = l + ((r - l) >> 1);
    if(x <= mid)
        change(lc, l, mid, x, v);
    else
        change(rc, mid+1, r, x, v);
    pushup(p);
}
qw get(int p, int l, int r, int L, int R){
    if(L <= l && r <= R)
        return tr[p];
    int mid = l + ((r - l) >> 1);
    qw res = {-1, 0x3f3f3f3f};
    if(L <= mid)
        res = check(res, get(lc, l, mid, L, R));
    if(mid < R)
        res = check(res, get(rc, mid+1, r, L, R));
    return res;
}
signed main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> m;
    for(int i = 1; i <= m; i++){
        cin >> a[i].a >> a[i].b;
        diff[a[i].a].push_back(a[i].b);
        cnt[a[i].a]++;
    }
    build(1, 1, n);
    for(int k = 1; k <= n; k++){
        change(1, 1, n, k, -0x3f3f3f3f);
        for(int i = 0; i < diff[k].size(); i++){
            change(1, 1, n, diff[k][i], 1);
        }
        cout << get(1, 1, n, 1, n).b << endl;
        change(1, 1, n, k, 0x3f3f3f3f);
        for(int i = 0; i < diff[k].size(); i++){
            change(1, 1, n, diff[k][i], -1);
        }
    }
}