自动搬运

查看原文

来自洛谷，原作者为

	xtzqhy 2023.7-2024.11||AFO

搬运于2025-08-24 22:56:21，当前版本为作者最后更新于2024-11-14 22:29:58，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

感觉和[Cnoi2019] 须臾幻境的离线版很像啊。

首先可以把期望拆掉，答案为 $\frac {\text{所有连通块的权值和的平方和-所有点的权值的平方和}}{n(n-1)}$。

考虑莫队。加边是容易的，可以并查集维护。但删边是困难的，所以考虑回滚莫队，用可撤销并查集实现回滚。

然后剩下的就是基础的回滚莫队了。

复杂度 $O(n\sqrt n \log n)$。

#include"bits/stdc++.h"
#define re register
#define int long long
#define pii pair<int,int>
#define fi first
#define se second
using namespace std;
const int maxn=1e5+10,maxm=500,mod=1e9+7;
int n,m,Q,siz,tot,bs;
int a[maxn],ans[maxn];
int st[maxm],ed[maxm],bel[maxn<<1];
struct edge{
    int u,v;
}e[maxn<<1];
struct query{
    int l,r,id;
}q[maxn];
struct dsu{
    int fa[maxn],siz[maxn],w[maxn];
    stack<pii> stk;
    inline int find(int x){if(x!=fa[x]) return find(fa[x]);return fa[x];}
    inline void merge(int u,int v,int &now,bool type){
        int x=find(u),y=find(v);
        if(x==y){if(type) stk.push({0,0});return;}
        if(siz[x]<siz[y]) swap(x,y);
        if(type) stk.push({x,y});
        now=((now-w[x]*w[x]%mod-w[y]*w[y]%mod)%mod+mod)%mod;
        siz[x]+=siz[y],fa[y]=x,w[x]=(w[x]+w[y])%mod;
        now=(now+w[x]*w[x]%mod)%mod;
    }
    inline void undo(){
        int x=stk.top().fi,fi,y=stk.top().se;stk.pop();
        fa[y]=y,siz[x]-=siz[y],w[x]=((w[x]-w[y])%mod+mod)%mod;
    }
}t1,t2;
inline bool cmp(query a,query b){
    if(bel[a.l]==bel[b.l]) return a.r<b.r;
    return bel[a.l]<bel[b.l];
}
inline int qpow(int a,int b){
    int res=1;
    while(b){
        if(b&1) res=res*a%mod;
        b>>=1;
        a=a*a%mod; 
    }
    return res;
}
inline int Inv(int x){return qpow(x,mod-2);}
inline void init(){
    siz=sqrt(m);
    tot=m/siz;
    for(re int i=1;i<=tot;++i) st[i]=(i-1)*siz+1,ed[i]=i*siz;
    if(ed[tot]<m) ++tot,st[tot]=ed[tot-1]+1,ed[tot]=m;
    for(re int i=1;i<=tot;++i) for(re int j=st[i];j<=ed[i];++j) bel[j]=i;
}
inline void solve(int l,int r,int id){
    int res=bs;
    for(re int i=l;i<=r;++i) t2.merge(e[i].u,e[i].v,res,1);
    ans[id]=((res-bs)%mod+mod)%mod;
    for(re int i=l;i<=r;++i) t2.undo();
}
inline void add(int id,int &res,bool type){t1.merge(e[id].u,e[id].v,res,type);}
signed main(){
#ifndef ONLINE_JUDGE
    freopen("1.in","r",stdin);
    freopen("1.out","w",stdout);
#endif
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n>>m>>Q;
    for(re int i=1;i<=n;++i) cin>>a[i],bs=(bs+a[i]*a[i])%mod;
    for(re int i=1;i<=n;++i) t1.fa[i]=i,t1.siz[i]=1,t1.w[i]=a[i];
    for(re int i=1;i<=n;++i) t2.fa[i]=i,t2.siz[i]=1,t2.w[i]=a[i];
    for(re int i=1;i<=m;++i) cin>>e[i].u>>e[i].v;
    for(re int i=1;i<=Q;++i) cin>>q[i].l>>q[i].r,q[i].id=i;
    init();
    sort(q+1,q+Q+1,cmp);
    int l=1,r=0,lst=0,now=bs;
    for(re int i=1;i<=Q;++i){
        if(bel[q[i].l]==bel[q[i].r]) solve(q[i].l,q[i].r,q[i].id);
        else{
            if(lst^bel[q[i].l]){
                for(re int i=1;i<=n;++i) t1.fa[i]=i,t1.siz[i]=1,t1.w[i]=a[i];
                l=ed[bel[q[i].l]]+1,r=ed[bel[q[i].l]];
                now=bs,lst=bel[q[i].l];
            }
            while(r<q[i].r) add(++r,now,0);
            int tmp=now,l1=l;
            while(l1>q[i].l) add(--l1,tmp,1);
            ans[q[i].id]=((tmp-bs)%mod+mod)%mod;
            while(l1<l) l1++,t1.undo();
        }
    }
    for(re int i=1;i<=Q;++i) cout<<ans[i]*Inv(n*(n-1)%mod)%mod<<'\n';
    return 0;
}