场外菜鸡 whker 听说你谷添加国赛新题立刻前来围观
首先我们看到本题对于众数的定义，很容易想到通过权值线段树求解。（类似这题，但本题不需要可持久化）
对于一个序列，我们维护一个 deque 和一个动态开点权值线段树。deque 表示序列本身，线段树每个节点记录值在 \([l,r]\) 中的元素有多少个。
对于操作 \(1\)：
线段树对应位置 \(+1\)，同时 deque push_back。无需多说。
对于操作 \(2\)：
在 deque 中找到要删除的数，线段树对应位置 \(-1\)，同时 deque pop_back。也无需多说。
对于操作 \(3\)：
开一个 vector 存下所有被询问的节点，每次分别把左儿子和右儿子的总和求出来（相当于把合并序列变成合并节点），如果左边大于一半就向左边跳，如果右边大于一半就向右边跳，否则无解。
对于操作 \(4\)：
合并两个序列，就是分别合并这两个序列的 deque 和线段树。
对于合并线段树，其实是非常简单的。要把线段树 \(T_1,T_2\) 合并，并将结果存入 \(T_1\)，如果两棵树都存在能表示 \([l,r]\) 的节点，只需要将两节点相加，否则选择存在的那个节点。
对于合并 deque，暴力一个一个 push_back 必然超时，因此考虑启发式合并，每次把长度较小的那个挨个 push 到长度较大的那个中去。需要注意的是要保证顺序，也就是应该 push_back 还是 push_front 的问题。这也是使用 deque 而不是 vector 的原因。
以上两个合并操作的时间复杂度在均摊后都是 \(O(n\log n)\) 的，严格证明需要势能分析，然而我不会，所以我只能靠直觉（悲）。
此外这题要开 long long，因为操作 \(3\) 不保证 \(x_1, \ldots, x_m\) 互不相同，可能加爆。（不开会 WA#16）
代码：
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
constexpr int N = 5e5 + 5, M = 1e6;
struct node {
int ls, rs;
ll cnt;
};
/*vector<node> nd;
int nnd(int& p) {
if(p) return p;
nd.push_back({0, 0, 0});
return p = nd.size() - 1;
}*/
//用vector会出现申必的RE
node nd[N * 24];
int tot = -1;
#define nnd(p) p ? p : (p = ++tot)
struct SGT {
deque<int> a;
int rt;
SGT() {
a.clear();
//nd.push_back({0, 0, 0});
//rt = nd.size() - 1;
rt = ++tot;
}
void add(int p, int l, int r, int loc, int val) {
nd[p].cnt += val;
if(l == r) return;
int mid = (l + r) >> 1;
if(loc <= mid) add(nnd(nd[p].ls), l, mid, loc, val);
else add(nnd(nd[p].rs), mid + 1, r, loc, val);
}
void ins(int v) {
a.push_back(v);
add(rt, 1, M, v, 1);
}
void pop() {
add(rt, 1, M, *a.rbegin(), -1);
a.pop_back();
}
}tr[N];
int n, q, ptr[M + 5];
int query(vector<int>& p, int l, int r, ll m) {
if(l == r) return l;
ll lsum = 0, rsum = 0;
int mid = (l + r) >> 1;
for(auto i : p)
lsum += nd[nd[i].ls].cnt, rsum += nd[nd[i].rs].cnt;
if(lsum > m) {
for(auto &i : p) i = nd[i].ls;
return query(p, l, mid, m);
}
else if(rsum > m) {
for(auto &i : p) i = nd[i].rs;
return query(p, mid + 1, r, m);
}
else return -1;
}
int merge(int x, int y, int l, int r) {
if(!x) return y;
if(!y) return x;
nd[x].cnt += nd[y].cnt;
if(l == r) return x;
int mid = (l + r) >> 1;
nd[x].ls = merge(nd[x].ls, nd[y].ls, l, mid);
nd[x].rs = merge(nd[x].rs, nd[y].rs, mid + 1, r);
return x;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> n >> q;
iota(ptr + 1, ptr + n + 1, 1);
for(int i = 1; i <= n; ++i) {
int l; cin >> l;
for(int j = 1; j <= l; ++j) {
int x; cin >> x;
tr[i].ins(x);
}
//cerr << i << ' ' << tot << endl;
}
while(q--) {
int op, x, y, z;
cin >> op >> x;
if(op == 1) cin >> y, tr[ptr[x]].ins(y);
else if(op == 2) tr[ptr[x]].pop();
else if(op == 3) {
vector<int> p;
ll l = 0;
while(x--) {
int xx; cin >> xx;
l += tr[ptr[xx]].a.size();
p.push_back(tr[ptr[xx]].rt);
}
cout << query(p, 1, M, l >> 1) << endl;
}
else if(op == 4) {
cin >> y >> z;
if(tr[ptr[x]].a.size() > tr[ptr[y]].a.size()) {
ptr[z] = ptr[x];
for(auto i : tr[ptr[y]].a) tr[ptr[x]].a.push_back(i);
tr[ptr[x]].rt = merge(tr[ptr[x]].rt, tr[ptr[y]].rt, 1, M);
}
else {
ptr[z] = ptr[y];
for(auto i = tr[ptr[x]].a.rbegin(); i != tr[ptr[x]].a.rend(); ++i)
tr[ptr[y]].a.push_front(*i);
tr[ptr[y]].rt = merge(tr[ptr[y]].rt, tr[ptr[x]].rt, 1, M);
}
}
}
return 0;
}
事后了解到这题开 \(10^6\) 个 deque 在 CCF 的机子上是会 MLE 爆零的，其实完全可以用 list，再不济手写链表也行。