Dyd's Blog

He who has a strong enough why can bear almost any how.

luoguP3765 总统选举

Posted on Edited on In
Symbols count in article: 4.7k Reading time ≈ 4 mins.

心血来潮想写SBT了

总统选举

想写平衡树了，所以看了道题

前置

首先有一个小小的前置知识：摩尔投票法

摩尔投票法用来寻找数组中出现次数超过一半的元素

思想很简单，考虑每次取两个不同的数，把他们都删掉，如果有一个数出现次数超过一半的话，最后剩下的数一定都是这个数，正确性显然

具体实现可以考虑维护一个 cnt 和 t ，扫描每一个元素，若 cnt = 0 ，则令 t = x ，否则 cnt += (t == x ? 1 : -1) ， 最后如果 cnt 大于 $0$ ， t 即是出现次数超过一半的元素

但这里有一个条件，那就是必须保证出现次数超过一半的元素存在，否则 t 当然就不是所求，所以我们还需要判断一下 t 的出现次数是否超过一半

题

那么考虑这道题

由摩尔投票法，对于每个区间我们只需要维护出 cnt 和 t

考虑道维护的东西可以合并，即对于 $fa = [l, r], lc = [l, mid], rc = [mid + 1, r]$ ，有：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
if (v[lc] == v[rc])
{
    v[fa] = v[lc];
    cnt[fa] = cnt[lc] + cnt[rc];
}
else if (cnt[lc] >= cnt[rc])
{
    cnt[fa] = cnt[lc] - cnt[rc];
    v[fa] = v[lc];
}
else
{
    cnt[fa] = cnt[rc] - cnt[lc];
    v[fa] = v[rc];
}

正确性显然

所以可以考虑用线段树维护 cnt 和 t （就是上面的 v ）

但是！问题来了：摩尔投票法有一个讨厌的前提——必须保证出现次数超过一半的元素存在，所以我们还要检验这个数是否真的是出现次数超过一半的数

考虑平衡树，对于每一个候选人，建一棵平衡树，维护支持他的人的下标，直接查询 l - 1 和 r 在平衡树中的排名即可得到在 $[l, r]$ 中有多少人支持他

卡了个最优（主要是SBT快），估计现在已经没了吧

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
//SBT yyds
#include <bits/stdc++.h>
#define STC static
#define IL inline
using namespace std;
const int N = 5e5 + 5, K = 1e6 + 5;

struct NodeForSBT
{
    int l, r, v, si;
    #define l(x) node_for_sbt[(x)].l
    #define r(x) node_for_sbt[(x)].r
    #define v(x) node_for_sbt[(x)].v
    #define si(x) node_for_sbt[(x)].si
} node_for_sbt[N + K]; //由于del优化,SBT的节点数为n+插入节点数
int num = 0;
struct SBT
{
    int rt = 0;
    IL void rr(int &t)
    {
        int k = l(t);
        l(t) = r(k), r(k) = t;
        si(k) = si(t);
        si(t) = si(l(t)) + si(r(t)) + 1;
        t = k;
    }
    IL void lr(int &t)
    {
        int k = r(t);
        r(t) = l(k), l(k) = t;
        si(k) = si(t);
        si(t) = si(l(t)) + si(r(t)) + 1;
        t = k;
    }
    IL void mt(int &t, bool f)
    {
        if (!f)
        {
            if (si(l(l(t))) > si(r(t)))
                rr(t);
            else if (si(r(l(t))) > si(r(t)))
                lr(l(t)), rr(t);
            else
                return ;
        }
        else
        {
            if (si(r(r(t))) > si(l(t)))
                lr(t);
            else if (si(l(r(t))) > si(l(t)))
                rr(r(t)), lr(t);
            else
                return ;
        }
        mt(l(t), false);
        mt(r(t), true);
        mt(t, false), mt(t, true);
    }
    IL void ins(int &t, int v)
    {
        if (!t)
        {
            t = ++num;
            node_for_sbt[t] = {0, 0, v, 1};
            return ;
        }
        ++si(t);
        if (v <= v(t))
            ins(l(t), v);
        else
            ins(r(t), v);
        mt(t, v > v(t));
    }
    IL int del(int &t, int v)
    {
        --si(t); //一定要先减,不然会错
        if ((v(t) == v) || (v(t) < v && !r(t)) || (v(t) > v && !l(t)))
        {
            int res = v(t);
            if (!l(t) || !r(t))
                t = l(t) + r(t);
            else
                v(t) = del(l(t), v(t) + 1);
            return res;
        }
        //在这里--si(t)就会错
        return v(t) < v ? del(r(t), v) : del(l(t), v);
    }
    IL int rk(int &t, int v)
    {
        if (!t)
            return 0;
        if (v == v(t))
            return si(l(t)) + 1;
        return v < v(t) ? rk(l(t), v) : si(l(t)) + 1 + rk(r(t), v);
    }
} sbt[N];
struct LineTree
{
    struct Date
    {
        int cnt, v;
    } ;
    struct NodeForLineTree
    {
        int l, r;
        Date dat;
        #define ll(x) node_for_line_tree[(x)].l
        #define rr(x) node_for_line_tree[(x)].r
        #define ct(x) node_for_line_tree[(x)].dat.cnt
        #define vv(x) node_for_line_tree[(x)].dat.v
    } node_for_line_tree[N << 2];
    #define lc (u << 1)
    #define rc (u << 1 | 1)
    #define Mid (ll(u) + rr(u) >> 1)
    IL void merge(Date x, Date y, Date &z) //合并x和y,储存在z
    {
        if (x.v == y.v)
            z.v = x.v, z.cnt = x.cnt + y.cnt;
        else if (x.cnt >= y.cnt)
            z.v = x.v, z.cnt = x.cnt - y.cnt;
        else
            z.v = y.v, z.cnt = y.cnt - x.cnt;
    }
    IL void up(int u)
    {
        merge(node_for_line_tree[lc].dat, node_for_line_tree[rc].dat, node_for_line_tree[u].dat);
    }
    IL void build(int u, int l, int r, int x[])
    {
        ll(u) = l, rr(u) = r;
        if (l == r)
        {
            ct(u) = 1, vv(u) = x[l];
            return ;
        }
        int mid = Mid;
        build(lc, l, mid, x), build(rc, mid + 1, r, x);
        up(u);
    }
    IL void change(int u, int pos, int d)
    {
        if (ll(u) == rr(u))
        {
            ct(u) = 1, vv(u) = d;
            return ;
        }
        int mid = Mid;
        if (pos <= mid)
            change(lc, pos, d);
        else
            change(rc, pos, d);
        up(u);
    }
    IL Date ask(int u, int l, int r)
    {
        if (ll(u) >= l && rr(u) <= r)
            return {ct(u), vv(u)};
        int mid = Mid;
        Date res = {0, 0};
        if (l <= mid)
            merge(ask(lc, l, r), res, res);
        if (r > mid)
            merge(ask(rc, l, r), res, res);
        return res;
    }
} lt;
IL bool check(int x, int l, int r)
{
    int t = sbt[x].rk(sbt[x].rt, r) - sbt[x].rk(sbt[x].rt, l - 1);
    return (t << 1) > (r - l + 1);
}

int main()
{
    int n, m;
    STC int a[N];
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; ++i)
    {
        scanf("%d", &a[i]);
        sbt[a[i]].ins(sbt[a[i]].rt, i);
    }
    lt.build(1, 1, n, a);
    int l, r, s, k, win, t;
    while (m--)
    {
        scanf("%d%d%d%d", &l, &r, &s, &k);
        win = lt.ask(1, l, r).v;
        if (!check(win, l, r))
            win = s;
        printf("%d\n", win);
        for (int i = 1; i <= k; ++i)
        {
            scanf("%d", &t);
            lt.change(1, t, win);
            sbt[a[t]].del(sbt[a[t]].rt, t);
            sbt[win].ins(sbt[win].rt, t);
            a[t] = win;
        }
    }
    win = lt.ask(1, 1, n).v;
    if (check(win, l, r))
        printf("%d\n", win);
    else
        printf("-1\n");
    return 0;
}