CF763E-题解

· · 题解

1.基本思路

观察到题目反复询问连续区间的一种难以统计的权值，时间为 7s 。不难想到使用莫队。

同时，题目询问的问题和联通块数量有关，考虑使用并查集维护。

想要同时处理点增加和删除是很困难的，尝试使用回滚莫队，单独对增加操作进行处理。

总体时间复杂度 O(n \sqrt{n} \log n) 。

2.具体细节

由于我们有 k \leq 5 的限制，我们可以对每一个点存两个 vector 分别表示当前点与左边（编号更小）和右边（编号更大）的哪些点有连边，每个点最多只会占用 O(k) 的空间。

接下来我们再仔细看一下回滚莫队的细节。

利用可撤销并查集暴力合并，然后暴力撤销，单次时间复杂度 O(\sqrt{n}\log n) 。

对块外的部分先用并查集扩展，然后对块内部分进行扩展，统计答案后对块内部分撤销。

除此之外，要注意到我们新增点时加边不要超出询问 [l,r] 的限制。

代码：

#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
const int N=500005;

int n,k,m,q,Ans[N],cnn,nowr;
vector<int> tol[N],tor[N];
struct query{int l,r,id;}Q[N];
int pos[N],_R[N],BAS;

int prt[N],siz[N];
stack< pair<int,int> > s;
int fa(int s){return prt[s]==s?s:fa(prt[s]);}
int merge(int x,int y)
{
    x=fa(x),y=fa(y);
    if(x==y) return 0;
    if(siz[x]>siz[y]) swap(x,y);
    prt[x]=y,siz[y]+=siz[x];
    s.push({x,y});
    return 1;
}
void del(int tot=s.size())
{
    while(tot--)
    {
        int x=s.top().first,y=s.top().second; s.pop();
        prt[x]=x,siz[y]-=siz[x];
    }
}

int add(int u,int lim,int tp)
{
    ++cnn;
    int rec=0;
    for(auto v:tp?tor[u]:tol[u])
        if((tp?v<=lim:v>=lim)) rec+=merge(u,v);
    cnn-=rec;
    return rec;
}
int main()
{
    scanf("%d %d %d",&n,&k,&m);
    BAS=(int)sqrt(n);
    for(int i=1;i<=n;++i)
        prt[i]=i,siz[i]=1,pos[i]=(i-1)/BAS+1,_R[pos[i]]=i;

    for(int i=1,x,y;i<=m;++i)
    {
        scanf("%d %d",&x,&y);
        if(x>y) swap(x,y);
        tor[x].push_back(y),tol[y].push_back(x);
    }
    scanf("%d",&q);
    for(int i=1;i<=q;++i) scanf("%d %d",&Q[i].l,&Q[i].r),Q[i].id=i;

    sort(Q+1,Q+q+1,[](query a,query b){return pos[a.l]==pos[b.l]?a.r<b.r:pos[a.l]<pos[b.l];});
    for(int i=1;i<=q;++i)
    {
        int l=Q[i].l,r=Q[i].r;
        if(pos[l]!=pos[Q[i-1].l] || (pos[Q[i-1].l]==pos[Q[i-1].r]&&pos[l]!=pos[r]))
            del(),cnn=0,nowr=_R[pos[l]];
        if(pos[l]==pos[r])
        {
            cnn=0;
            for(int j=l,tmp;j<=r;++j) tmp=add(j,l,0);
            Ans[Q[i].id]=cnn;
            del();
        }
        else
        {
            int tmp=0,ctt=0;
            while(nowr+1<=r) tmp=add(++nowr,_R[pos[l]]+1,0);
            int tmpcnn=cnn;
            for(int j=_R[pos[l]];j>=l;--j) ctt+=add(j,nowr,1);
            Ans[Q[i].id]=cnn;
            del(ctt),cnn=tmpcnn;
        }
    }
    for(int i=1;i<=q;++i) printf("%d\n",Ans[i]);
}