题意回顾

我们需要维护 $n$ 个序列，支持：

1. 在序列末尾插入/删除元素
2. 合并两个序列（操作4，新建序列并删除原序列）
3. 查询多个序列拼接后的绝对众数（出现次数 > 总长度一半）

数据范围：$n, q \le 5\times 10^5$，总操作序列长度 $C_m \le 5\times 10^5$。

核心思路

1. 绝对众数的性质

如果一个数 $x$ 在序列中出现次数严格大于总长度的一半，那么它一定是绝对众数。

关键性质（摩尔投票法）：

• 如果存在绝对众数，那么它一定是序列中任意一部分的众数候选者之一
• 我们可以用"对拼法"合并多个序列的候选者

具体来说：

• 维护一个候选值 $cand$ 和计数器 $cnt$
• 遍历元素：
  • 如果 $cnt = 0$，设 $cand = x$，$cnt = 1$
  • 否则如果 $x = cand$，则 $cnt++$
  • 否则 $cnt--$
• 最后 $cand$ 是可能的绝对众数候选，需要验证出现次数

2. 数据结构设计

由于需要支持快速合并（操作4），使用启发式合并。

对每个序列维护：

• 一个双向链表（或动态数组）存储元素
• 一个哈希表记录每个值的出现次数
• 序列长度 $len$
• 序列的摩尔投票信息（候选值和计数）

3. 操作实现

操作1：插入

• 在链表末尾插入元素
• 更新哈希表：$count[y]++$
• 更新序列长度
• 更新摩尔投票信息（可选）

操作2：删除

• 从链表末尾删除元素
• 更新哈希表：$count[last]--$
• 更新序列长度

操作4：合并

• 采用启发式合并：将较小序列的元素插入到较大序列中
• 时间复杂度：$O(\min(|A|, |B|))$
• 总复杂度：$O((n+q)\log(n+q))$

操作3：查询众数

1. 候选阶段：

   • 初始化 $cand = -1$，$cnt = 0$
   • 遍历所有被拼接的序列，用摩尔投票法合并候选者
   • 具体合并方法：

     for 每个序列的候选值 c 和计数 t:
         if cnt == 0:
             cand = c, cnt = t
         else if cand == c:
             cnt += t
         else:
             cnt = abs(cnt - t)
             if cnt == 0: cand = -1
     

2. 验证阶段：

   • 如果 $cand = -1$，直接返回 $-1$
   • 否则统计 $cand$ 在所有拼接序列中的总出现次数
   • 如果出现次数 $> \frac{\text{总长度}}{2}$，返回 $cand$，否则返回 $-1$

复杂度分析

• 初始序列总长度 $C_l \le 5\times 10^5$
• 所有插入操作最多增加 $q$ 个元素
• 启发式合并总复杂度：$O((n+q)\log(n+q))$
• 查询操作总复杂度：$O(C_m + \text{总长度})$，在数据范围内可接受

代码实现

#include <bits/stdc++.h>
using namespace std;

struct Sequence {
    list<int> elements;
    unordered_map<int, int> count;
    int len;
    int candidate;
    int candidate_cnt;
    
    Sequence() : len(0), candidate(-1), candidate_cnt(0) {}
    
    void update_candidate(int x) {
        if (candidate_cnt == 0) {
            candidate = x;
            candidate_cnt = 1;
        } else if (candidate == x) {
            candidate_cnt++;
        } else {
            candidate_cnt--;
            if (candidate_cnt == 0) candidate = -1;
        }
    }
    
    void push_back(int x) {
        elements.push_back(x);
        count[x]++;
        len++;
        update_candidate(x);
    }
    
    void pop_back() {
        if (elements.empty()) return;
        int x = elements.back();
        elements.pop_back();
        count[x]--;
        len--;
        // 需要重新计算候选者（简单实现：遍历）
        candidate = -1;
        candidate_cnt = 0;
        for (auto elem : elements) {
            update_candidate(elem);
        }
    }
    
    int get_count(int x) const {
        auto it = count.find(x);
        return it == count.end() ? 0 : it->second;
    }
};

vector<Sequence> seqs;

void merge_sequences(int x1, int x2, int x3) {
    Sequence& s1 = seqs[x1];
    Sequence& s2 = seqs[x2];
    
    // 启发式合并：总是合并到新的序列
    Sequence new_seq;
    
    // 将s1的元素加入新序列
    for (int elem : s1.elements) {
        new_seq.push_back(elem);
    }
    
    // 将s2的元素加入新序列
    for (int elem : s2.elements) {
        new_seq.push_back(elem);
    }
    
    seqs[x3] = move(new_seq);
}

int query_sequences(const vector<int>& indices) {
    // 第一阶段：找候选者
    int cand = -1, cnt = 0;
    
    for (int idx : indices) {
        const Sequence& s = seqs[idx];
        if (s.candidate == -1) continue;
        
        if (cnt == 0) {
            cand = s.candidate;
            cnt = s.candidate_cnt;
        } else if (cand == s.candidate) {
            cnt += s.candidate_cnt;
        } else {
            cnt = abs(cnt - s.candidate_cnt);
            if (cnt == 0) cand = -1;
        }
    }
    
    if (cand == -1) return -1;
    
    // 第二阶段：验证
    int total_len = 0;
    int total_count = 0;
    
    for (int idx : indices) {
        const Sequence& s = seqs[idx];
        total_len += s.len;
        total_count += s.get_count(cand);
    }
    
    if (total_count * 2 > total_len) {
        return cand;
    } else {
        return -1;
    }
}

int main() {
    int n, q;
    cin >> n >> q;
    
    seqs.resize(n + q + 5);
    
    // 读入初始序列
    for (int i = 1; i <= n; i++) {
        int len;
        cin >> len;
        for (int j = 0; j < len; j++) {
            int x;
            cin >> x;
            seqs[i].push_back(x);
        }
    }
    
    // 处理操作
    for (int i = 0; i < q; i++) {
        int op;
        cin >> op;
        
        if (op == 1) {
            int x, y;
            cin >> x >> y;
            seqs[x].push_back(y);
        } else if (op == 2) {
            int x;
            cin >> x;
            seqs[x].pop_back();
        } else if (op == 3) {
            int m;
            cin >> m;
            vector<int> indices(m);
            for (int j = 0; j < m; j++) {
                cin >> indices[j];
            }
            cout << query_sequences(indices) << endl;
        } else if (op == 4) {
            int x1, x2, x3;
            cin >> x1 >> x2 >> x3;
            merge_sequences(x1, x2, x3);
        }
    }
    
    return 0;
}

总结

本题的关键在于：

1. 利用摩尔投票法的可合并性质处理多个序列的众数查询
2. 采用启发式合并高效处理序列合并操作
3. 分离候选和验证阶段保证正确性
4. 合理选择数据结构平衡时间和空间复杂度