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

· · 题解

简单题。

首先 | S\cup T| = |S|+|T|-|S\cap T|。考虑求 |S\cap T| 即可。

对于每种颜色的出现次数阈值分治，设阈值为 B。

对于出现次数 \ge B 的颜色，只有 \mathcal{O}(n/B) 个，开个 bitset 跑暴力即可做到 \mathcal{O}(n/Bw)。

对于出现次数 <B 的颜色，考虑到有 \mathcal{O}(B^2) 个询问点对包含它。枚举这些点对，所有颜色共有 \mathcal{O}(nB) 个，做单点加即可。

然后由于只有 \mathcal{O}(n) 次询问，我们只需加到有询问的点对上，这样第二部分的空间是线性的。

取 B=\sqrt{n/w}，时空复杂度均为 \mathcal{O}(n\sqrt{n/w})。

然而空间不太够用。

第一部分将这些次数 \ge B 的颜色每 K 一组处理。空间复杂度变为 \mathcal{O}(nK/w)，时间复杂度加上 \mathcal{O}(n^2/BK)。

取 K=w，空间变为线性，时间复杂度仍为 \mathcal{O}(n\sqrt{n/w})。

#include<bits/stdc++.h>
#define ull unsigned long long
#define rd read()
#define gc pa == pb && (pb = (pa = buf) + fread(buf, 1, 400000, stdin), pa == pb) ? EOF : *pa++
#define gt(x,y) (1ull*x*n+y)
using namespace std;
static char buf[400000], * pa(buf), * pb(buf);
inline int read()
{
    unsigned int x=0,s=gc;while(s<48)s=gc;
    while(s>=48)x=(x<<1)+(x<<3)+(s^48),s=gc;
    return x;
}
const int N=1000001,K=64,B=40;
int n,siz[N],sz[N],ans[N],d[N],t[N];ull b[N];
basic_string<int> v,P[N];unordered_map<ull,int> mp;
struct qu{int op,x,y;}q[N];
inline void sol()
{
    for(int i=1;i<=n;++i)
    {
        if(q[i].op==1&&~d[q[i].y])b[q[i].x]|=(1ull<<d[q[i].y]);
        if(q[i].op==2&&(b[q[i].x]|b[q[i].y]))ans[i]+=__builtin_popcountll(b[q[i].x]|b[q[i].y]);
    }
    for(int i=1;i<=n;++i)b[i]=0;for(int i:v)d[i]=-1;v.clear();
}
signed main()
{
    n=rd,memset(d,-1,sizeof(d));
    for(int i=1;i<=n;++i)q[i]={rd,rd,rd},siz[q[i].y]+=(q[i].op==1);
    for(int i=1;i<=n;++i)
    {
        if(q[i].op==2)mp[gt(q[i].x,q[i].y)]=mp[gt(q[i].y,q[i].x)]=i;
        if(siz[i]>=B)d[i]=v.size(),v.push_back(i);if(v.size()==K)sol();
    }
    if(v.size())sol();
    for(int i=1;i<=n;++i)
    {
        auto [op,x,y]=q[i];
        if(op==1&&siz[y]<B){P[y].push_back(x);for(int j:P[y])if(mp.count(gt(x,j)))++t[mp[gt(x,j)]];++sz[x];}
        if(op==2){ans[i]+=sz[x]+sz[y];if(sz[x]&&sz[y])ans[i]-=t[mp[gt(x,y)]];}
    }
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    for(int i=1;i<=n;++i)if(q[i].op==2)cout<<ans[i]<<'\n';return 0;
}