P8496 (NOI2022 d1t1) 题解

· · 题解

前言

这里是考场上半小时想到标算半小时码完然后链表写挂只有 85pts 的选手。果然我适合滚回普及组补习。

这题上来就是一个 #define 众数 绝对众数 的操作。看到求绝对众数，想到摩尔投票法。

前置知识：不了解摩尔投票法的珂以看一下 P2397，我认为这是摩尔投票法板题。

思路就是，若序列存在绝对众数，那么每次删去序列中两个值不同的数，直到只剩下一个值时一定是绝对众数。这个应该很好理解。

具体到这题，如何维护一个带修序列的绝对众数呢？

理解摩尔投票法的原理后，自然容易想到它的一个性质：

具体地，删除顺序不影响最终结果。

注意到这题的插入、删除操作都只影响一个数，所以使用线段树维护序列，每个线段树节点维护当前区间在摩尔投票法下的信息（出现次数最多的值及其剩余的出现次数）。

那么 pushup 操作就相当于摩尔投票法中删数的过程。由于序列长度不定，我们使用权值线段树，并动态开点。由于我们只关心整个序列的绝对众数，于是我们只需要单点修改和全局查询。

对于插入、删除操作，注意到每次只在序列尾部进行操作，于是再使用一个链表维护序列，同时线段树单点修改即可。

对于合并操作，线段树合并即可解决，这里不展开讲解了。同时还需要合并链表。

对于询问操作，我们定义一个与线段树节点类型相同的变量，将其与每个序列对应的线段树根节点进行如 pushup 一般的操作，就能得到一个答案。

别忘了，摩尔投票法求得绝对众数的前提是序列存在绝对众数，所以我们还需要检验答案。

在线段树上记录相应值的出现次数，这样就能用刚才的答案进行若干次单点查询求得它在序列中的出现次数，与序列长度比较即可。

放一下改到 AC 的删除注释和 freopen 的考场代码。

#include<cstdio>
using namespace std;
const int N=1e6+3;
struct node{
    int siz,ans,num;
    node operator +(const node &y)const{
        node tmp;
        tmp.siz=siz+y.siz;
        if(ans==y.ans) tmp.ans=ans,tmp.num=num+y.num;
        else if(num>y.num) tmp.ans=ans,tmp.num=num-y.num;
        else tmp.ans=y.ans,tmp.num=y.num-num;
        return tmp;
    }
};
struct seg{
    int l,r;node x;
}t[N*22];
void pushup(int x){
    t[x].x=t[t[x].l].x+t[t[x].r].x;
}
struct seq{
    int x,lst,nxt;
}a[N];
int n,m,q,cnt,tot,hd[N],tl[N],rt[N],que[N];
void add(int &x,int l,int r,int L,int k){
    if(!x) x=++cnt;
    if(l==r){
        t[x].x={t[x].x.siz+k,l,t[x].x.siz+k};
        return;
    }
    int mid=(l+r)>>1;
    L>mid?add(t[x].r,mid+1,r,L,k):add(t[x].l,l,mid,L,k);
    pushup(x);
}
int query(int x,int l,int r,int L){
    if(l==r) return t[x].x.siz;
    int mid=(l+r)>>1;
    return L>mid?query(t[x].r,mid+1,r,L):query(t[x].l,l,mid,L);
}
void mergeseg(int &x,int y,int l,int r){
    if(!y) return;
    if(!x){x=y;return;}
    if(l==r){t[x].x=t[x].x+t[y].x;return;}
    int mid=(l+r)>>1;
    mergeseg(t[x].l,t[y].l,l,mid);
    mergeseg(t[x].r,t[y].r,mid+1,r);
    pushup(x);
}
int main(){
    scanf("%d%d",&n,&q),m=n+q;
    for(int i=1,k;i<=n;++i){
        scanf("%d",&k);
        hd[i]=tot+1;
        for(int x;k--;){
            scanf("%d",&x);
            ++tot;
            a[tot]={x,tot-1,tot+1};
            add(rt[i],1,m,x,1);
        }
        tl[i]=tot;
    }
    for(int op,x,y,z;q--;){
        scanf("%d",&op);
        if(op==1){
            scanf("%d%d",&x,&y);
            a[++tot]={y,tl[x],0};
            (t[rt[x]].x.siz?a[tl[x]].nxt:hd[x])=tot;
            tl[x]=tot;
            add(rt[x],1,m,y,1);
        }
        if(op==2){
            scanf("%d",&x);
            add(rt[x],1,m,a[tl[x]].x,-1);
            tl[x]=a[tl[x]].lst;
        }
        if(op==3){
            node tmp={0,0,0};
            scanf("%d",&x);
            for(int i=1;i<=x;++i){
                scanf("%d",que+i);
                tmp=tmp+t[rt[que[i]]].x;
            }
            int num=0;
            for(int i=1;i<=x;++i)
                num+=query(rt[que[i]],1,m,tmp.ans);
            printf("%d\n",num*2>tmp.siz?tmp.ans:-1);
        }
        if(op==4){
            scanf("%d%d%d",&x,&y,&z);
            if(t[rt[x]].x.siz)
                hd[z]=hd[x],a[tl[x]].nxt=hd[y];
            else hd[z]=hd[y];
            if(t[rt[y]].x.siz)
                tl[z]=tl[y],a[hd[y]].lst=tl[x];
            else tl[z]=tl[x];
            mergeseg(rt[x],rt[y],1,m);
            rt[z]=rt[x];
        }
    }
    return 0;
}

后话

珂以去看一道思路相似的题目 P3765 总统选举，上面的图片就截自这题的讨论区。

前言说的“链表写挂”具体是指合并操作中合并链表时忘记判空，导致头尾指针可能丢失信息。最终是一名 SC 老哥帮我看出来的，感谢他/bx/bx。

这题询问时序列珂以重复，所以统计出现次数时理论最大能达到 (5\cdot10^5)^2 会爆 int。但是良心出题人没卡这个，幸好幸好。所以我就用了 int，日后我要是因为这个原因被 hack 了就不用喊我改了自己想办法（（（

我省队长帮我调代码时评价我的线段树合并写法比较神奇，同时对我手写链表的行为表示不满：“我在考场上想了 10mins 要不要写链表最后决定不写，结果最后还是得调链表。”

我省 E 队爷说使用 STL list 就不用合并时判空了，看来得学学 list。愧对 id 的屑

讲题人钦定线段树是标算并表示场切选手没有使用这种做法的，令人感叹。