P8496 [NOI2022] 众数

· · 题解

每个序列开一颗动态开点权值线段树，每个节点维护子树和，那么 1 操作相当于单点加，4 操作相当于合并 2 颗线段树。

考虑 3 操作，可以同时在这 m 颗线段树上二分，设众数出现次数需要 \ge need，那么众数能出现在 [l,r] 内当且仅当区间 [l,r] 内的数个数 \ge need，由于线段树上每个区间的两段子区间中最多只会有一段满足要求，判断哪段符合要求并递归处理，最后在递归到子节点时判断当前数是否合法。

但是只有权值线段树无法得知序列最后一个数是什么，那么可以对每个序列开一个链表，维护每个序列的开头、末尾、每个数的值以及每个数上一个数是什么，那么合并两个序列时只需要把 2 个链表接在一起，删数时取出链表末尾的数并修改线段树上的对应位置。

注意 3 操作后得到的序列长度可能会超出 int 的范围，需要开 long long。

//People who believe in miracles are as amazing as miracles themselves.
#include<bits/stdc++.h>
#define ll long long
using namespace std;
inline ll read(){
    ll x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-') f=-f;ch=getchar();}
    while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
    return x*f;
}

const int N=1e6+10;
int n,q,m,len[N],val[N],ed[N],st[N],pre[N],rt[N],cnt,tot,p[N],num; ll need;

#define mid ((l+r)>>1)
struct node{
    int ls,rs,num;
}tr[N*25];
void chg(int &x,int l,int r,int p,int k){
    if(!x) x=++tot; tr[x].num+=k;
    if(l!=r) p<=mid?chg(tr[x].ls,l,mid,p,k):chg(tr[x].rs,mid+1,r,p,k);
}
int merge(int x,int y,int l,int r){
    if(!x||!y) return x+y;
    if(l==r) return tr[x].num+=tr[y].num,x;
    tr[x].ls=merge(tr[x].ls,tr[y].ls,l,mid);
    tr[x].rs=merge(tr[x].rs,tr[y].rs,mid+1,r);
    return tr[x].num=tr[tr[x].ls].num+tr[tr[x].rs].num,x;
}
int que(int l,int r){
    ll sum=0;
    if(l==r){
        for(int i=1;i<=num;++i) sum+=tr[p[i]].num; return sum>=need?l:-1;
    }
    for(int i=1;i<=num;++i) sum+=tr[tr[p[i]].ls].num;
    if(sum>=need){
        for(int i=1;i<=num;++i) p[i]=tr[p[i]].ls; return que(l,mid);
    }
    else{
        for(int i=1;i<=num;++i) p[i]=tr[p[i]].rs; return que(mid+1,r);
    }
}

signed main(){
    n=read(),q=read(),m=n+q;
    for(int i=1;i<=n;++i){
        len[i]=read();
        for(int j=1;j<=len[i];++j){
            ++cnt;
            if(!st[i]) st[i]=cnt; else pre[cnt]=ed[i];
            val[cnt]=read(),chg(rt[i],1,m,val[cnt],1),ed[i]=cnt;
        }
    }
    for(int op,x,y,z;q;--q){
        op=read();
        if(op==1){
            x=read(),y=read(),++len[x],++cnt;
            if(!st[x]) st[x]=cnt; else pre[cnt]=ed[x];
            val[cnt]=y,chg(rt[x],1,m,y,1),ed[x]=cnt;
        }
        else if(op==2){
            x=read(),--len[x];
            chg(rt[x],1,m,val[ed[x]],-1),ed[x]=pre[ed[x]]; if(!ed[x]) st[x]=0;
        }
        else if(op==3){
            num=read(),need=0;
            for(int i=1;i<=num;++i) p[i]=read(),need+=len[p[i]],p[i]=rt[p[i]];
            need=need/2+1,printf("%d\n",que(1,m));
        }
        else{
            x=read(),y=read(),z=read();
            len[z]=len[x]+len[y];
            if(st[x]&&st[y]) st[z]=st[x],ed[z]=ed[y],pre[st[y]]=ed[x];
            else if(st[x]) st[z]=st[x],ed[z]=ed[x];
            else if(st[y]) st[z]=st[y],ed[z]=ed[y];
            rt[z]=merge(rt[x],rt[y],1,m),rt[x]=rt[y]=st[x]=st[y]=ed[x]=ed[y]=len[x]=len[y]=0;
        }
    }
    return 0;
}