题解：P5607 [Ynoi2013] 无力回天 NOI2017

· · 题解

先把两个集合的并的大小换成两个集合大小之和减交的大小，问题变成如何快速查询两个集合的交。我们有两种暴力，一种是直接做集合的交，另一种是从元素对查询的贡献入手，维护拥有某个元素的集合的集合，维护一张 m\times m 的表直接表示答案，每次加入新的集合暴力扫一遍之前已经加入的集合更新答案。

第一种暴力可以用 bitset 优化，第二种暴力，设最终拥有元素 i 的集合有 s_i 个，则要更新答案

\sum_{i=1}^m \frac{s_i(s_i-1)}{2}

次。考虑对两种暴力根号分治平衡复杂度，对 s_i\leq S 的元素做第二种暴力，对剩下的 O(\frac{m}{S}) 个元素做第一种暴力。暴力一的复杂度为 O(\frac{m^2}{Sw})，暴力二的复杂度为 O(mS)，取 S=\sqrt{\frac{m}{w}} 可得到最优复杂度 O(m\sqrt{\frac{m}{w}})。

然后还有些问题，首先 bitset 开太多空间要炸（没有炸太多），但是由于所有 bitset 中为 1 的位置总共不超过 m 个，所以考虑当有至少两个元素的时候再开辟 bitset 的内存，这样空间可以减半；最后是关于 m\times m 的表如何维护，直接上哈希表常数会爆炸，但我们可以离线处理，把每次修改看成一个二元组 (a,b)，查询拆成 (x_1,x_2),(x_2,x_1)（x_1=x_2 时特判），表示查已经插入的二元组中有多少个跟我一样。对于第一维的每种取值都开个链表，按时间顺序将修改跟查询插入，统计贡献时开个桶处理第二维就好了。由于要存下所有修改，空间也是 O(m\sqrt{\frac{m}{w}}) 的。

如果被卡常记得调一调块长。下面给个参考代码：

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MAXM=1e6,S=100,B=(MAXM-1)/(S+1)+1,SIZE=MAXM*S/2+2*MAXM;

int Read()
{
    int res=0;char c;
    while(!isdigit(c=getchar()));
    while(isdigit(c)) res=res*10+c-'0',c=getchar();
    return res;
}
void Print(int x)
{
    if(x<10) {putchar('0'+x);return;}
    int y=x/10;
    Print(y);
    putchar('0'+x-y*10);
}

int m,opt[MAXM+5],X[MAXM+5],Y[MAXM+5];
bitset<B> Set[MAXM/2+5];
int SID[MAXM+5],Single[MAXM+5],snum;
vector<int> Q[MAXM+5];
int buc[MAXM+5],Code[MAXM+5],tot;
int cnt[MAXM+5];
int ans[MAXM+5],qry[SIZE+5],lst[MAXM+5]; 

int Cap(int a,int b)
{
    if(!SID[a] || !SID[b]) return 0;
    if(SID[a]>0 && SID[b]>0) return (Set[SID[a]]&Set[SID[b]]).count();
    if(SID[a]>0) return Set[SID[a]][Single[b]];
    if(SID[b]>0) return Set[SID[b]][Single[a]];
    return Single[a]==Single[b];
}

int main()
{
    m=Read();
    for(int i=1;i<=m;i++)
    {
        opt[i]=Read(),X[i]=Read(),Y[i]=Read();
        if(opt[i]==1) ++buc[Y[i]];
    }
    for(int i=1;i<=m;i++) if(buc[i]>S) Code[i]=tot++;
    for(int i=1;i<=m;i++)
        if(opt[i]==1) {if(buc[Y[i]]<=S) lst[X[i]]+=cnt[Y[i]]++;}
        else if(X[i]!=Y[i]) ++lst[X[i]],++lst[Y[i]];
    for(int i=1;i<=m;i++) lst[i]+=lst[i-1];
    for(int i=m;i;i--) cnt[i]=0,lst[i]=lst[i-1];
    for(int i=1;i<=m;i++)
        if(opt[i]==1)
        {
            ++cnt[X[i]];
            if(buc[Y[i]]<=S)
            {
                for(int j=0;j<Q[Y[i]].size();j++) qry[++lst[X[i]]]=Q[Y[i]][j];
                Q[Y[i]].push_back(X[i]);
            }
            else
            {
                if(!SID[X[i]]) {Single[X[i]]=Code[Y[i]],SID[X[i]]=-1;continue;}
                if(SID[X[i]]<0) Set[SID[X[i]]=++snum][Single[X[i]]]=1;
                Set[SID[X[i]]][Code[Y[i]]]=1;
            }
        }
        else
        {
            if(X[i]==Y[i]) {ans[i]=cnt[X[i]];continue;}
            ans[i]=cnt[X[i]]+cnt[Y[i]]-Cap(X[i],Y[i]);
            qry[++lst[X[i]]]=qry[++lst[Y[i]]]=-i;
        }
    for(int i=1;i<=m;i++) cnt[i]=0;
    for(int i=1;i<=m;i++)
    {
        for(int j=lst[i-1]+1;j<=lst[i];j++)
            if(qry[j]>0) ++cnt[qry[j]];
            else
            {
                int v=-qry[j];
                if(i==X[v]) ans[v]-=cnt[Y[v]];
                else ans[v]-=cnt[X[v]];
            }
        for(int j=lst[i-1]+1;j<=lst[i];j++) if(qry[j]>0) --cnt[qry[j]];
    }
    for(int i=1;i<=m;i++) if(opt[i]==2) Print(ans[i]),putchar('\n');
    return 0;
}