题解 [NOI2022] 众数

· · 题解

啥也不会的赛后补题选手来一发题解。

题面

题目定义的“众数”为序列中出现次数严格大于一半的数字，先考虑只有一个序列的做法。

我们可以对序列建立一颗权值线段树，查询时往左右子区间中元素个数大于原序列长度一半的方向递归查找，如果都小于则无解。这样操作的时间复杂度是 \log_2 n 的。

要维护多个序列，我们对每个序列都建立一棵权值线段树。因为权值线段树不能维护序列的顺序，所以需要使用vector记录整个序列的内容，方便插入删除。

对于 1 操作，向权值线段树及vector中同时加入新元素即可。对于 2 操作，我们找到所删除序列的权值线段树和vector，在权值线段树和vector中删除此vector里最靠后的元素。

对于 4 操作，题目要求两个序列拼接并删除原序列。

考虑线段树合并。将前面序列的权值线段树合并到后面序列的权值线段树上即可。有一个问题：对应存储序列的vector无法合并。

那我们就不合并vector，维护一个链表样的东西，记录当前下标的序列前面所接的序列。同时记录每个序列最后一个元素所在的vector。这样操作 1 时在当前最后一个元素所在的vector插入元素，操作 2 时则直接删除即可。若当前序列末尾所在vector已经为空，那么可以一直跳链表，直到当前所在的vector不为空为止。

为提高合并效率，需要额外维护并查集记录当前vector在所属序列最合并位置靠前的vector下标，

对于 3 操作，题目要求多个序列拼接后的众数。

合并多棵线段树的复杂度无法接受。那该怎么做？暴力！我们按照单颗权值线段树的做法，同时对多棵线段树查询。对于左右子区间的元素个数，我们可以每次暴力遍历所有查询树的当前节点并求和。

这样复杂度为什么是对的？题目中保证了查询的序列总数不超过 5 \times 10^5，而每次查询有 \log n 层，则对于所有询问暴力求和的总次数为 n \log n 级别。

这样我们就解决了这个问题。

注意事项：

  1. 本题操作 3 的序列可以重复，因此求区间元素总个数时可能会爆long long。

  2. deque空间复杂度极高，使用需谨慎。

  3. 合并两个序列时不要暴力跳链找序列首，可以使用并查集维护加速查找。

代码

#include <cstdio>
#include <vector>
const int Nx=1000010;
int N,Q;
std::vector<int> a[Nx];
int vl[Nx],chain[Nx],nid[Nx],fa[Nx];
int siz[80*Nx],ls[80*Nx],rs[80*Nx],cnt,root[Nx];
int new_node(){return ++cnt;}
void addin(int ll,int rr,int &p,int pos,int delta)
{
    if(!p)
        p=new_node();
    if(ll==rr)
    {
        siz[p]+=delta;
        return;
    }
    int mid=(ll+rr)>>1;
    if(pos<=mid)
        addin(ll,mid,ls[p],pos,delta);
    else
        addin(mid+1,rr,rs[p],pos,delta);
    siz[p]=siz[ls[p]]+siz[rs[p]];
}
int find_vec(int ll,int rr,std::vector<int> p,long long szp,long long flen)
{
    if(szp<flen)
        return -1;
    if(ll==rr)
        return ll;
    long long sizl=0,sizr=0;
    int mid=(ll+rr)>>1;
    std::vector<int> lc,rc;
    for(auto i : p)
    {
        sizl+=siz[ls[i]];
        sizr+=siz[rs[i]];
        lc.push_back(ls[i]);
        rc.push_back(rs[i]);
    }
    if(sizl>=flen)
        return find_vec(ll,mid,lc,sizl,flen);
    if(sizr>=flen)
        return find_vec(mid+1,rr,rc,sizr,flen);
    return -1;
}
int merge(int x,int y)
{
    if(!x||!y)
        return x+y;
    if(!ls[x]&&!rs[x])
    {
        siz[x]+=siz[y];
        return x;
    }
    ls[x]=merge(ls[x],ls[y]);
    rs[x]=merge(rs[x],rs[y]);
    siz[x]=siz[ls[x]]+siz[rs[x]];
    return x;
}
int ff(int p)
{
    if(p!=fa[p])
        fa[p]=ff(fa[p]);
    return fa[p];
}
int main()
{
    scanf("%d%d",&N,&Q);
    int i,j,k,val,opt,x,y;
    for(i=1;i<=N;i++)
    {
        scanf("%d",&vl[i]);
        for(j=1;j<=vl[i];j++)
        {
            scanf("%d",&val);
            a[i].push_back(val);
            addin(0,Nx,root[i],val,1);
        }
    }
    for(i=1;i<Nx;i++)
        chain[i]=i,nid[i]=i,fa[i]=i;
    while(Q--)
    {
        scanf("%d",&opt);
        if(opt==1)
        {
            scanf("%d%d",&x,&y);
            a[nid[x]].push_back(y);
            addin(0,Nx,root[x],y,1);
        }
        else if(opt==2)
        {
            scanf("%d",&x);
            while(a[nid[x]].size()==0)
                nid[x]=chain[nid[x]];
            val=a[nid[x]][a[nid[x]].size()-1];
            a[nid[x]].pop_back();
            addin(0,Nx,root[x],val,-1);
        }
        else if(opt==3)
        {
            scanf("%d",&k);
            std::vector<int> qv;
            long long sza=0;
            for(j=1;j<=k;j++)
            {
                scanf("%d",&val);
                qv.push_back(root[val]);
                sza+=siz[root[val]];
            }
            printf("%d\n",find_vec(0,Nx,qv,sza,sza/2+1));
        }
        else if(opt==4)
        {
            scanf("%d%d%d",&x,&y,&val);
            root[val]=merge(root[x],root[y]);
            nid[val]=nid[y];
            k=ff(nid[y]);
            chain[k]=nid[x];
            fa[k]=nid[x];
        }
    }
}

不知道为什么跑得比较慢...