P8496 [NOI2022] 众数 题解
UPD：同学提醒我值域是从
感觉是 day1 唯一一个我能看懂的题了（悲）。
一看就像是数据结构题。我们不妨先考虑对于单个序列的删除、插入和查询操作怎么快速实现。我们可以对这个序列开一棵权值线段树，这样就能实现快速地删除和插入了。线段树的节点维护对应值域区间内出现次数最多的值以及这个值出现的次数。查询的时候看一下这个值的出现次数是否超过序列长度一半即可。
对于多个序列呢？我们对每个序列都做上面的事情，但是序列的合并和查询十分棘手。
考虑两个序列合并。首先把两个序列对应的线段树合并起来是容易做的（线段树要动态开点），但是这还不够，我们得把这两个序列真的拼起来，而不仅仅是完成值域信息的拼接。很多人想到了用 deque 维护每个序列，然后合并的时候启发式合并，暴力地把小的序列插到大的序列中（根据题目要求决定前端还是后端插入）。但是吧，赛后已经众所周知的一点，deque 这东西的预留空间有亿点大，导致很多想到正解的选手超出空间限制。我们考虑使用链表维护。链表可以支持快速地删除末尾元素，在末尾插入元素，以及把两个链表顺次拼接。注意代码实现的时候，拼接时不一定两个序列全都非空，不注意这个可能会挂分。
然后考虑最有意思的查询。这里需要先介绍一下摩尔投票法（下文的“众数”都是题目中的定义，而不是更为常见的那个含义）。
摩尔投票法的核心思想为对拼消耗，考虑一个序列，我们每次取出两个数，如果相同就放回，不同的话就抵消，把这两个数全都删除，直到序列为空或剩一种数。如果序列空了就说明它没有众数，否则剩下的这种数就可能是这个序列的众数。注意被其他的数绝不可能成为答案，剩下的这个是不是答案还需要检验。经典的应用有 P3765 总统选举。可以用线段树维护可能的众数，然后用平衡树检查这是否是众数。
回到这个题，首先一个结论，如果有解，则最终的答案必然是至少一个被询问到的序列的众数。显然是正确的：如果一个数在任何一个序列出现的次数都不超过一半，那么把序列都拼起来自然也不会超过一半。我们称存在众数的序列为“可贡献的序列”，其余为“不可贡献的序列”。我们考虑对可贡献的序列进行摩尔投票（因为答案只有可能在这里产生），比较方便的做法是每个可贡献序列的众数先和这个序列中其余的数进行抵消，然后把每个序列经过内部抵消后的众数再拿出来进行摩尔投票。代码实现的时候维护当前答案和它出现的次数，把所有可贡献序列扫一遍不断更新答案即可。然后我们最后找到一个可能成为答案的数，再检验一遍即可，把被询问的所有序列扫一遍，在每个线段树上查这个数的出现次数然后加起来，看是不是所有序列拼接后的众数。
这里可能有人会问（包括我也有过这个疑惑）：为什么不可贡献的序列在寻找可能成为答案的数的时候可以直接忽略？如果把这些序列也加入考虑，摩尔投票的结果会产生变化吧？（即选出的数是另一个可贡献的序列的众数）
这样考虑：如果把不可贡献序列加入考虑后摩尔投票的结果发生变化，那么此次询问必然无解，由于检验操作的存在，不影响最终答案。为什么必然无解？如果只考虑可贡献序列，可能的答案为
细节：询问时统计数字出现次数时记得开 long long；注意值域是从
代码：
#include<bits/stdc++.h>
using namespace std;
int read(){
int ss=0,ww=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-')
ww=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
ss=ss*10+ch-'0';
ch=getchar();
}
return ss*ww;
}
const int N=1000010;
int s[N],n,q;
int node;
struct ST{
int ls;
int rs;
int sum;
int dat;
}st[N*30];
int rt[N];
void add(int &root,int l,int r,int x,int k){
if(!root)
root=++node;
if(l==r){
st[root].sum+=k;
st[root].dat=l;
return;
}
int mid=(l+r)/2;
if(mid>=x)
add(st[root].ls,l,mid,x,k);
else
add(st[root].rs,mid+1,r,x,k);
if(st[st[root].ls].sum>st[st[root].rs].sum){
st[root].sum=st[st[root].ls].sum;
st[root].dat=st[st[root].ls].dat;
}
else{
st[root].sum=st[st[root].rs].sum;
st[root].dat=st[st[root].rs].dat;
}
}
ST ask(int root,int l,int r,int x){
if(l==r)
return st[root];
int mid=(l+r)/2;
if(mid>=x)
return ask(st[root].ls,l,mid,x);
else
return ask(st[root].rs,mid+1,r,x);
}
void merge(int &root,int p,int q,int l,int r){
if(!p){
root=q;
return;
}
if(!q){
root=p;
return;
}
if(!root)
root=++node;
if(l==r){
st[root].sum=st[p].sum+st[q].sum;
st[root].dat=l;
return;
}
int mid=(l+r)/2;
merge(st[root].ls,st[p].ls,st[q].ls,l,mid);
merge(st[root].rs,st[p].rs,st[q].rs,mid+1,r);
if(st[st[root].ls].sum>st[st[root].rs].sum){
st[root].sum=st[st[root].ls].sum;
st[root].dat=st[st[root].ls].dat;
}
else{
st[root].sum=st[st[root].rs].sum;
st[root].dat=st[st[root].rs].dat;
}
}
int fst[N],lst[N],pre[N],val[N];
int id;
void push_back(int x,int y){//第 x 个序列后插入 y
id++;
if(!fst[x])
fst[x]=id;
val[id]=y;
pre[id]=lst[x];
lst[x]=id;
}
int sz[N];//序列长度
int x[N];
int main(){
//freopen("major.in","r",stdin);
//freopen("major.out","w",stdout);
n=read();
q=read();
for(int i=1;i<=n;i++){
int m;
m=read();
sz[i]=m;
for(int j=1;j<=m;j++){
int x;
x=read()+1;
push_back(i,x);
add(rt[i],0,n+q+1,x,1);
}
}
for(int i=1;i<=q;i++){
int opt;
opt=read();
if(opt==1){
int x,y;
x=read();
y=read()+1;
push_back(x,y);
add(rt[x],0,n+q+1,y,1);
sz[x]++;
}
if(opt==2){
int x;
x=read();
add(rt[x],0,n+q+1,val[lst[x]],-1);
lst[x]=pre[lst[x]];
sz[x]--;
if(!sz[x])
fst[x]=0;
}
if(opt==3){
int m;
m=read();
for(int j=1;j<=m;j++)
x[j]=read();
pair<int,long long> nw;
nw={0,0};
long long tot=0;
for(int j=1;j<=m;j++){
tot+=sz[x[j]];
if(st[rt[x[j]]].sum<=sz[x[j]]/2)//判断一个序列有无众数
continue;
long long res=st[rt[x[j]]].sum-(sz[x[j]]-st[rt[x[j]]].sum);//该序列众数和序列中其他数进行抵消
if(st[rt[x[j]]].dat==nw.first){//如果这个数和当前答案相同，合并
nw.second+=res;
continue;
}
if(nw.second==res){//恰好抵消了
nw={0,0};
continue;
}
if(nw.second<res){//更新答案，并进行抵消
nw={st[rt[x[j]]].dat,res-nw.second};
continue;
}
if(nw.second>res)//不更新，但是抵消一次
nw.second-=res;
}
long long ans=0;
if(!nw.first){//全都抵消了，没有众数
cout<<"-1\n";
continue;
}
for(int j=1;j<=m;j++)//检查的过程
ans+=ask(rt[x[j]],0,n+q+1,nw.first).sum;
if(ans>tot/2)//如果合法
cout<<nw.first-1<<'\n';
else
cout<<"-1\n";
}
if(opt==4){
int a,b,c;
a=read();
b=read();
c=read();
merge(rt[c],rt[a],rt[b],0,n+q+1);
if(lst[b])
lst[c]=lst[b];
else
lst[c]=lst[a];
if(fst[a])
fst[c]=fst[a];
else
fst[c]=fst[b];
if(fst[b])
pre[fst[b]]=lst[a];
sz[c]=sz[a]+sz[b];
sz[a]=sz[b]=fst[a]=fst[b]=lst[a]=lst[b]=0;
}
}
return 0;
}