关于我一分钟口胡切了 NOI 送分题这件事

yummy · 2022-08-30 00:20:34 · 题解

缘起

NOI 刚刚结束，但是《因为疫情的不确定性》，NOI 同步赛取消，因此我很长一段时间看不到真题。

后来我请 mrsrz 帮忙复述了简要题意，然后我说瞬间就想起来某道经典题目：很小的空间限制求绝对众数。

我和 mrsrz 说“我怀疑这题混进提高组模拟赛可能都分不出来”，然后她表示相当惊讶，后来我才发现，我做法比她少一个 log。

所以为啥我今天才写这道题呢？

• 一方面，洛谷当时还在讨论是否公开 NOI 题目。
• 另一方面，我这半个月都在练习数据结构，因此我想把知识点搭配一下，口味更加自然。

但是，今天我想了想，NOI 题，给点面子。

做这题之前，请确保您会线段树合并。

前置知识：二进制拆位法求绝对众数

这篇题解和楼上不同，因为我不会维护摩尔投票法。

该方法和摩尔投票法一样，能求出唯一可能是答案的方法。

其实这方法不是我原创的，我能找到该方法最早的出处是： https://www.luogu.com.cn/blog/daks/solution-p2397。

简要复述一下该方法：对于一个序列 a，对于每个二进制位 b，求有多少个数该位是 1，记作 cnt_b。

存在绝对众数 m 时，如果 m 某一位是 1，那么 cnt_b 一定过半，反则一定不过半。

这个方法好处是可以巨方便地合并两个序列。

维护序列 a

这个序列 a 显然必须维护。不然的话，2 操作删掉了一个谁都不知道。所以 2 操作目的就是考一个链表？

观察到每次我们都只用到 a 的末尾，以及归并，我们可以使用链表维护数列 a。

因为我比较懒（而且链表是 O(n) 的，不是复杂度瓶颈），所以我选择用 STL。我们发现 4 操作本质相当于把 x_2 接到 x_1 后面，然后把 x_1 重命名为 x_3。

list 记录了 end()，可以 O(1) push_back 和 pop_back，所以这个复杂度不需要担心。

list 的 size() 函数在 C++ 11 起保证为 O(1)，在此之前可能是 O(1) 或线性，因此如果你提交本题代码建议选择 C++ 14。

将 list2 接到 list1 末尾表示为 list1.splice(list1.end(),list2)。该函数复杂度为 O(1)。

判 -1

我们维护二进制拆位求众数，算出一个可能的众数，接下来要判断该数是否过半。

这时候我们发现，线段树合并逃不掉了。对于每个序列我们还要额外维护一个动态开点线段树，方便查询可能的众数出现次数是否过半。

计算一下复杂度，发现是 1\log 的。但是我不知道为啥跑了 600 多毫秒，毕竟维护二进制拆位常数看着很小。

然后就差不多啦，贴代码：

#include<bits/stdc++.h>
using namespace std;
struct SGT
{
    long long cnt;int ls,rs;//cnt只有叶子结点的才有用 
}tr[20000005];
int used=0;
int New(){used++;tr[used].cnt=0;tr[used].ls=tr[used].rs=0;return used;}
void upd(int rt,int pos,int up)//线段树更新
{
    for(int high=(1<<19);high;high>>=1)
    {
        if(pos&high)
        {
            if(tr[rt].rs==0)
                tr[rt].rs=New();
            rt=tr[rt].rs;
        }
        else
        {
            if(tr[rt].ls==0)
                tr[rt].ls=New();
            rt=tr[rt].ls;
        }
    }
    tr[rt].cnt+=up;
}
void merge(int rt,int frm)//线段树合并
{
    if(tr[frm].ls)
    {
        if(tr[rt].ls==0)
            tr[rt].ls=tr[frm].ls;
        else merge(tr[rt].ls,tr[frm].ls);
    }
    if(tr[frm].rs)
    {
        if(tr[rt].rs==0)
            tr[rt].rs=tr[frm].rs;
        else merge(tr[rt].rs,tr[frm].rs);
    }
    tr[rt].cnt+=tr[frm].cnt;
}
long long count(int rt,int pos)//线段树单点查询
{
    for(int high=(1<<19);high;high>>=1)
        if(pos&high)
            rt=tr[rt].rs;
        else
            rt=tr[rt].ls;
    return tr[rt].cnt;
}
struct Mode//维护二进制拆位
{
    long long a[20];
    Mode(){memset(a,0,sizeof a);}
    int mode(long long sz)//给出序列长求众数
    {
        int res=0;
        for(int i=0;i<20;i++)
            if(a[i]>sz/2)res|=1<<i;
        return res;
    }
}s[1000005];
void operator +=(Mode &m,int x)
{
    for(int i=0;i<20;i++)
        if(x&(1<<i))m.a[i]++;
}
void operator -=(Mode &m,int x)
{
    for(int i=0;i<20;i++)
        if(x&(1<<i))m.a[i]--;
}
void operator +=(Mode& x,Mode y)
{
    for(int i=0;i<20;i++)
        x.a[i]+=y.a[i];
}
int n,q,seq[500005];//seq记录每个序列对应线段树的根 
list<int> a[500005];
int quest[500005],to[1000005];
int main()
{
    int l,m,x,y;
    scanf("%d%d",&n,&q);
    for(int i=1;i<=n;i++)
    {
        to[i]=i;//to[i]记录每个序列的实际存储位置
        seq[i]=New();//每个序列开一个线段树
        for(scanf("%d",&l);l;l--)
        {
            scanf("%d",&x);
            a[i].push_back(x);//维护链表
            s[i]+=x;//维护二进制拆位
            upd(seq[i],x,1);//维护线段树
        }
    }
    for(;q;q--)
    {
        scanf("%d",&l);
        if(l==1)
        {
            scanf("%d%d",&x,&y);x=to[x];//全部数据存在真实位置，下同
            a[x].push_back(y);
            s[x]+=y;
            upd(seq[x],y,1);
        }
        if(l==2)
        {
            scanf("%d",&x);x=to[x];
            y=a[x].back();
            a[x].pop_back();
            s[x]-=y;
            upd(seq[x],y,-1);
        }
        if(l==3)
        {
            scanf("%d",&m);
            Mode tmp;
            long long tsz=0;//拼出来的序列总长
            for(int i=0;i<m;i++)
            {
                scanf("%d",&quest[i]);x=quest[i]=to[quest[i]];
                tmp+=s[x];//合并二进制拆位
                tsz+=a[x].size();
            }
            long long probable=tmp.mode(tsz),cnt=0;
            for(int i=0;i<m;i++)
                cnt+=count(seq[quest[i]],probable);
            if(cnt>tsz/2)
                printf("%d\n",probable);
            else puts("-1");
        }
        if(l==4)
        {
            scanf("%d%d%d",&x,&y,&m);
            x=to[x];y=to[y];
            merge(seq[x],seq[y]);//维护线段树
            to[m]=x;//重命名
            a[x].splice(a[x].end(),a[y]);//维护链表
            s[x]+=s[y];//维护二进制拆位
        }
    }
    return 0;
}