「NOI 2022」众数 - 线段树合并 + 链表

发表于 更新于 分类于 ， 阅读次数： Disqus：

题意描述

洛谷链接

LibreOJ 链接

对于一个序列，定义其众数为序列中出现次数严格大于一半的数字。注意该定义与一般的定义有出入，在本题中请以题面中给出的定义为准。

一开始给定 \(n\) 个长度不一的正整数序列，编号为 \(1 \sim n\)，初始序列可以为空。这 \(n\) 个序列被视为存在，其他编号对应的序列视为不存在。

有 \(q\) 次操作，操作有以下类型:

  • \(1 \ x \ y\)：在 \(x\) 号序列末尾插入数字 \(y\)。保证 \(x\) 号序列存在，且 \(1 \le x, y \le n + q\)。
  • \(2 \ x\)：删除 \(x\) 号序列末尾的数字，保证 \(x\) 号序列存在、非空，且 \(1 \le x \le n + q\)。
  • \(3 \ m \ x_1 \ x_2 \ x_m\)：将 \(x_1, x_2, \ldots, x_m\) 号序列顺次拼接，得到一个新序列，并询问其众数。如果不存在满足上述条件的数，则返回 \(-1\)。数据保证对于任意 \(1 \le i \le m\)，\(x_i\) 是一个仍然存在的序列，\(1 \le x_i \le n + q\)，且拼接得到的序列非空。注意：不保证 \(\boldsymbol{x_1, \ldots, x_m}\) 互不相同，询问中的合并操作不会对后续操作产生影响。
  • \(4 \ x_1 \ x_2 \ x_3\)：新建一个编号为 \(x_3\) 的序列，其为 \(x_1\) 号序列后顺次添加 \(x_2\) 号序列中数字得到的结果，然后删除 \(x_1, x_2\) 对应的序列。此时序列 \(x_3\) 视为存在，而序列 \(x_1, x_2\) 被视为不存在，在后续操作中也不会被再次使用。保证 \(1 \le x_1, x_2, x_3 \le n + q\)、\(x_1 \ne x_2\)、序列 \(x_1, x_2\) 在操作前存在、且在操作前没有序列使用过编号 \(x_3\)。

假定 \(C_l = \sum l_i\) 代表输入序列长度之和，\(C_m = \sum m\) 代表所有操作 \(3\) 需要拼接的序列个数之和；对于所有测试数据，保证 \(1 \le n, q, C_m, C_l \le 5 \times {10}^5\)。

解题思路

本题显然是一道数据结构题。对于序列的插入、删除和拼接，我们可以用 std::list 链表完成。对于每个序列的众数，我们可以对每个序列都开一颗线段树，统计序列众数。由于不确定序列长度，我们可以使用权值线段树 + 动态开点解决。权值线段树维护区间最大值及最大值的下标，即众数的出现次数和众数的下标。对于序列合并操作可用线段树合并解决。

接下来我们需要解决查询操作。对于查询操作我们直接新建线段树然后用线段树合并会 TLE，实际得分 80pts，于是我们需要寻找更优的方法。

对于寻找本题中的众数（我们将其定义为绝对众数），我们可以用 摩尔投票 解决。对于一个拥有绝对众数的序列，我们不停地消去序列中两个不同的数，最后剩下的一个数或多个相同的数即为这个序列的绝对众数（而对于不一定有绝对众数的序列，最终答案需带回检验），这种方法叫做摩尔投票。同时我们可以发现，对于多个序列总共的绝对众数，摩尔投票具有结合律，即我们将每个序列进行摩尔投票剩下来的数一起再进行一次摩尔投票，得到的结果即为所有序列总共的绝对众数。

接下来我们就可以用摩尔投票解决查询操作：我们先新建一个空序列 \(\text{res}\)，然后遍历每个询问的序列（每个序列的绝对众数可用先线段树查询众数，然后将二倍众数出现次数与序列长度比较即可得出）：

  • 若没有绝对众数，则这个序列对答案没有贡献，跳过；
  • 若有绝对众数，则通过众数出现次数及序列长度算出这个序列进行摩尔投票的结果 \(\text{now}\)，然后将 \(\text{res}\) 和 \(\text{now}\) 进行摩尔投票，结果存储于 \(\text{res}\)。

这样我们就得出了这些序列的可能的绝对众数 \(p\)。接下来再遍历一遍询问的序列，用线段树统计 \(p\) 的出现次数，最后再将二倍 \(p\) 的出现次数与这些序列的总长度比较即可得出 \(p\) 是否为这些序列总共的绝对众数。

时间复杂度为 \(O(n \log n)\)。

代码演示

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
#include <cstdio>
#include <iostream>
#include <list>

const int MAXN = 5e5;

struct SegT {
    int l, r;
    SegT *lc, *rc;
    std::pair<long long, int> val;

    SegT(int l, int r, SegT *lc, SegT *rc) : l(l), r(r), lc(lc), rc(rc), val(std::make_pair(0, 0)) {}
    SegT(int l, int r, SegT *lc, SegT *rc, std::pair<long long, int> val) : l(l), r(r), lc(lc), rc(rc), val(val) {}

    static SegT *build(const int l, const int r) {
        if (l > r) return NULL;
        else if (l == r) return new SegT(l, r, NULL, NULL, std::make_pair(0, l));
        else return new SegT(l, r, NULL, NULL);
    }

    void update(const int pos, const long long delta) {
        if (pos > this->r || pos < this->l) return;
        else if (pos == this->l && pos == this->r) val.first += delta;
        else {
            int mid = l + (r - l) / 2;
            if (pos <= mid) {
                if (!lc) lc = build(l, mid);
                lc->update(pos, delta);
            } else {
                if (!rc) rc = build(mid + 1, r);
                rc->update(pos, delta);
            }
            std::pair<long long, int> res = std::make_pair(0, 0);
            if (lc) res = std::max(res, lc->val);
            if (rc) res = std::max(res, rc->val);
            val = res;
        }
    }

    std::pair<long long, int> query(const int pos) {
        if (pos > this->r || pos < this->l) return std::make_pair(0, 0);
        else if (this->l == this->r) return val;
        else {
            std::pair<long long, int> res = std::make_pair(0, 0);
            if (lc) res = std::max(res, lc->query(pos));
            if (rc) res = std::max(res, rc->query(pos));
            return res;
        }
    }

    static SegT *merge(SegT *u, SegT *v) {
        if (!u) return v;
        if (!v) return u;
        SegT *w = build(u->l, u->r);
        if (w->l == w->r) {
            w->val.first = u->val.first + v->val.first;
            return w;
        }

        w->lc = merge(u->lc, v->lc);
        w->rc = merge(u->rc, v->rc);
        std::pair<long long, int> res = std::make_pair(0, 0);
        if (w->lc) res = std::max(res, w->lc->val);
        if (w->rc) res = std::max(res, w->rc->val);
        w->val = res;

        return w;
    }
} *segment[2 * MAXN + 1];

int n, q;
long long l[2 * MAXN + 1];
std::list<int> a[2 * MAXN + 1];

inline int read() {
    int x = 0, w = 1;
    char ch = 0;
    while (ch < '0' || ch > '9') {
        if (ch == '-') w = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        x = x * 10 + (ch - '0');
        ch = getchar();
    }
    return x * w;
}

int main() {
    n = read(), q = read();
    for (int i = 1; i <= n; i++) {
        segment[i] = SegT::build(1, 2 * MAXN);
        l[i] = read();
        for (int j = 1; j <= l[i]; j++) {
            int x;
            x = read();
            segment[i]->update(x, 1);
            a[i].push_back(x);
        }
    }

    while (q--) {
        int cmd;
        cmd = read();

        if (cmd == 1) {
            int x, y;
            x = read(), y = read();
            segment[x]->update(y, 1);
            a[x].push_back(y);
            l[x]++;
        } else if (cmd == 2) {
            int x;
            x = read();
            segment[x]->update(a[x].back(), -1);
            a[x].pop_back();
            l[x]--;
        } else if (cmd == 3) {
            int m;
            static int x[MAXN + 1];
            m = read();
            for (int i = 1; i <= m; i++) x[i] = read();

            std::pair<long long, int> res = std::make_pair(0, 0);
            for (int i = 1; i <= m; i++) {
                if (2 * segment[x[i]]->val.first <= l[x[i]]) continue;
                std::pair<long long, int> now = std::make_pair(segment[x[i]]->val.first - (l[x[i]] - segment[x[i]]->val.first), segment[x[i]]->val.second);
                if (now.second == res.second) res.first += now.first;
                else if (now.first == res.first) res = std::make_pair(0, 0);
                else if (now.first > res.first) res = std::make_pair(now.first - res.first, now.second);
                else if (now.first < res.first) res.first -= now.first;
            }

            if (res.first == 0) puts("-1");
            else {
                long long cnt = 0, len = 0;
                for (int i = 1; i <= m; i++) {
                    cnt += segment[x[i]]->query(res.second).first;
                    len += l[x[i]];
                }
                printf("%d\n", 2 * cnt > len ? res.second : -1);
            }
        } else if (cmd == 4) {
            int x1, x2, x3;
            x1 = read(), x2 = read(), x3 = read();

            segment[x3] = SegT::build(1, 2 * MAXN);
            segment[x3] = SegT::merge(segment[x3], segment[x1]);
            segment[x3] = SegT::merge(segment[x3], segment[x2]);
            a[x3].splice(a[x3].end(), a[x1]);
            a[x3].splice(a[x3].end(), a[x2]);
            l[x3] = l[x1] + l[x2];
        }
    }

    return 0;
}