居然还没调出来？感觉是数据类型的问题，真是吓人。先把思路写一下吧。
题意
灵梦一共有 n n n 张符卡，每张卡都有一个能力值，对于第 i i i 张卡，它的能力值为 a i a_i ai，现在她想从中选出两张符卡并使用它们，灵梦发现，如果她同时打出了两张符卡 i , j i, j i,j，这两张符卡造成的伤害将会是 a i × a j a_i\times a_j ai×aj。
这些符卡之间有能力的冲突，灵梦会告诉你这些符卡的兼容性，具体而言这些符卡之间有 m m m 条关系，这些关系表明某两张符卡之间是兼容的，注意，如果符卡 i , j i, j i,j 兼容且符卡 j , k j, k j,k 兼容，那么符卡 i , k i, k i,k 也是兼容的，如果打出的两张符卡之间不是兼容的，那么它们造成的伤害为 0 0 0。
她很好奇符卡之间的兼容性会造成什么样的影响，所以她会询问你 q q q 次，每次告诉你一对正整数 l , r l, r l,r，意味着只有编号在区间 [ l , r ] [l, r] [l,r] 内的关系才会生效。
灵梦不想把魔理沙虐得太惨，所以她会随机从所有符卡中选出两张不同的符卡来打出，她想知道每次询问造成的伤害的期望值对 1 0 9 + 7 10^9 + 7 109+7 取模后是多少。
输入
4 4 4
5 8 2 7
3 1
1 4
3 2
1 4
2 4
1 2
2 3
3 3
输出
500000012
833333349
500000012
666666674
样例解释
对于第三组询问，只有 ( 1 , 4 ) , ( 2 , 3 ) (1, 4), (2, 3) (1,4),(2,3) 两对符卡之间是兼容的。
如果选择的符卡是 ( 1 , 2 ) (1, 2) (1,2)，那么它们不兼容，伤害值为 0 0 0，这种情况的概率是 1 6 \dfrac16 61。
如果选择的符卡是 ( 1 , 3 ) (1, 3) (1,3)，那么它们不兼容，伤害值为 0 0 0，这种情况的概率是 1 6 \dfrac16 61。
如果选择的符卡是 ( 1 , 4 ) (1, 4) (1,4)，它们兼容，伤害值为 a 1 × a 4 = 35 a_1\times a_4 = 35 a1×a4=35，这种情况的概率是 1 6 \dfrac16 61。
如果选择的符卡是 ( 2 , 3 ) (2, 3) (2,3)，它们兼容，伤害值为 a 2 × a 3 = 16 a_2\times a_3 = 16 a2×a3=16，这种情况的概率是 1 6 \dfrac16 61。
如果选择的符卡是 ( 2 , 4 ) (2, 4) (2,4)，那么它们不兼容，伤害值为 0 0 0，这种情况的概率是 1 6 \dfrac16 61。
以此类推，最终的期望值是 17 2 \dfrac{17}{2} 217，其在模 1 0 9 + 7 10^9 + 7 109+7 意义下等于 500000012 500000012 500000012。
1 ≤ n , q ≤ 1 0 5 , 1 ≤ m ≤ 2 n , 1 ≤ a i ≤ 1 0 9 , 1 ≤ l i ≤ r i ≤ m , 1 ≤ u i , v i ≤ n 1\le n, q\le 10^5, 1\le m\le 2n, 1\le a_i\le 10^9, 1\le l_i\le r_i\le m, 1\le u_i, v_i\le n 1≤n,q≤105,1≤m≤2n,1≤ai≤109,1≤li≤ri≤m,1≤ui,vi≤n。
思路
给定询问区间，说编号在 [ l , r ] [l,r] [l,r] 的符卡可以产生关系，仅当两张符卡兼容，考虑用莫队维护区间数据。
肯定是并查集的，但是如果做全局并查集肯定不正确，因为有可能区间内有两张符卡不兼容，而与询问区间外的一张卡产生关系。
因此为了保证正确性，我们需要动态地维护并查集。因为双指针需要移动，因此需要写一个可撤销并查集——进入知识盲区了，不过就是对需要撤销的点对打标记，后进先撤销，那不就是栈序吗。
struct dsu
{
stack<pll>stk;
ll fa[N],siz[N];
ll fz(ll x)
{
while(x!=fa[x])x=fa[x]=fa[fa[x]];
return x;
}
void join(ll u,ll v,bool tag)//tag:是否将被撤销
{
u=fz(u),v=fz(v);
if(u==v)
{
if(tag)stk.push(mk(0,0));
return;
}
if(siz[u]<siz[v])swap(u,v);//规定从属先后
if(tag)stk.push({u,v});
siz[u]+=siz[v];
fa[v]=u;
}
void cancel()//撤销
{
ll u=stk.top().fi,v=stk.top().se;
stk.pop();
fa[v]=v;
siz[u]-=siz[v];
}
void reset()
{
for(ll i=1;i<=n;i++)
{
fa[i]=i;
siz[i]=1;
sum[i]=a[i];
}
}
};
我们发现撤销其实并不好更新答案，因为栈里面维护的是所在连通块内祖先的点对，无法对应原始下标，因此考虑使用回滚莫队。就是将双指针拆成 l ∼ b r l\sim br l∼br 和 b r + 1 ∼ r br+1\sim r br+1∼r，右区间部分永久化，左区间部分回滚……这就是回滚莫队的套路了，可以前往上一篇文章粗略学习。
题目要求造成的伤害的期望值对 1 0 9 + 7 10^9 + 7 109+7 取模后是多少，拆掉期望就是 E = a n s n ( n − 1 ) 2 E=\frac{ans}{\frac {n(n-1)}{2}} E=2n(n−1)ans， a n s ans ans 为当前询问造成的最大伤害。
计算 a n s ans ans 就是妥妥的数学题了。我们假设一组连通块内有 a , b , c , d a,b,c,d a,b,c,d，答案就是 a b + b c + c d + d a ab+bc+cd+da ab+bc+cd+da，但是这样不好在并查集合并时直接查询，考虑式子变形：
= 1 2 ( 2 a b + 2 a c + 2 a d + 2 b c + 2 b d + 2 c d ) =\frac {1}{2}(2ab+2ac+2ad+2bc+2bd+2cd) =21(2ab+2ac+2ad+2bc+2bd+2cd)
= 1 2 [ a 2 + b 2 + c 2 + d 2 + 2 a b + 2 a c + 2 a d + 2 b c + 2 b d + 2 c d − ( a 2 + b 2 + c 2 + d 2 ) ] =\frac{1}{2}[a^2+b^2+c^2+d^2+2ab+2ac+2ad+2bc+2bd+2cd-(a^2+b^2+c^2+d^2)] =21[a2+b2+c2+d2+2ab+2ac+2ad+2bc+2bd+2cd−(a2+b2+c2+d2)]
= 1 2 [ a ( a + b + c + d ) + b ( a + b + c + d ) + c ( a + b + c + d ) + d ( a + b + c + d ) − ( a 2 + b 2 + c 2 + d 2 ) ] =\frac{1}{2}[a(a+b+c+d)+b(a+b+c+d)+c(a+b+c+d)+d(a+b+c+d)-(a^2+b^2+c^2+d^2)] =21[a(a+b+c+d)+b(a+b+c+d)+c(a+b+c+d)+d(a+b+c+d)−(a2+b2+c2+d2)]
= 1 2 [ ( a + b + c + d ) 2 − ( a 2 + b 2 + c 2 + d 2 ) ] =\frac{1}{2}[(a+b+c+d)^2-(a^2+b^2+c^2+d^2)] =21[(a+b+c+d)2−(a2+b2+c2+d2)]
即连通块内战斗力总和的平方，减去各符卡平方的和，再除以 2 2 2。
各符卡平方的和在计算答案数组时，再统一减去，可以先把动态答案 r e t ret ret 的初值修改为 ∑ i = 1 n a i 2 \displaystyle\sum_{i=1}^{n}a_i^2 i=1∑nai2，计算答案时方便得到相反数。
具体细节见代码：
代码
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define mk make_pair
#define pll pair<ll,ll>
#define fi first
#define se second
const ll N=1e5+9,mod=1e9+7;
ll n,t,m,a[N];
ll bSize,cnt_b,bel[N<<1],bl[N],br[N];
ll ret,ans[N];
ll sm[N];
struct dsu
{
stack<pll>stk;
ll fa[N],siz[N],sum[N];//sum:块内权值总和
ll fz(ll x)
{
while(x!=fa[x])x=fa[x]=fa[fa[x]];
return x;
}
void join(ll u,ll v,ll &ANS,bool tag)//tag:是否将被撤销
{
u=fz(u),v=fz(v);
if(u==v)
{
if(tag)stk.push(mk(0,0));
return;
}
if(siz[u]<siz[v])swap(u,v);
if(tag)stk.push({u,v});
ANS=((ANS-sum[u]*sum[u]%mod-sum[v]*sum[v]%mod)%mod+mod)%mod;
siz[u]+=siz[v];
fa[v]=u;
sum[u]=(sum[u]+sum[v])%mod;
ANS=(ANS+sum[u]*sum[u]%mod)%mod;
}
void cancel()//撤销
{
ll u=stk.top().fi,v=stk.top().se;
stk.pop();
fa[v]=v;
siz[u]-=siz[v];
sum[u]=((sum[u]-sum[v])%mod+mod)%mod;
}
void reset()
{
for(ll i=1;i<=n;i++)
{
fa[i]=i;
siz[i]=1;
sum[i]=a[i];
}
}
}d,d2;
struct bian
{
ll u,v;
}b[N<<1];
struct que
{
ll l,r,id;
}q[N];
bool cmp(que x,que y)
{
if(bel[x.l]!=bel[y.l])return bel[x.l]<bel[y.l];
return x.r<y.r;
}
void init()
{
bSize=sqrt(t);//对边数分块
cnt_b=t/bSize;
if(t%bSize)cnt_b++;
for(ll i=1;i<=t;i++)
bel[i]=(i-1)/bSize+1;
for(ll i=1;i<=cnt_b;i++)
{
bl[i]=(i-1)*bSize+1;
br[i]=i*bSize;
}
br[cnt_b]=t;
}
void add_r(ll x,ll &ANS)
{
d.join(b[x].u,b[x].v,ANS,0);
}
void add_l(ll x,ll &ANS)
{
d.join(b[x].u,b[x].v,ANS,1);
}
void del_l(ll x)
{
d.cancel();
}
ll qpow(ll x,ll k)
{
ll ret=1;
while(k)
{
if(k&1)ret=ret*x%mod;
x=x*x%mod;
k>>=1;
}
return ret;
}
int main()
{
scanf("%lld%lld%lld",&n,&t,&m);
ll inv=qpow(n*(n-1),mod-2),sqs=0;
for(ll i=1;i<=n;i++)
{
scanf("%lld",&a[i]);
sqs=(sqs+a[i]*a[i]%mod)%mod;
}
d.reset();
d2.reset();
init();
ret=sqs;
for(ll i=1;i<=t;i++)
{
ll u,v;
scanf("%lld%lld",&u,&v);
b[i]=(bian){u,v};
}
for(ll i=1;i<=m;i++)
{
ll l,r;
scanf("%lld%lld",&l,&r);
q[i]=(que){l,r,i};
}
sort(q+1,q+m+1,cmp);
ll l=1,r=0;
for(ll i=1;i<=m;i++)
{
if(bel[q[i].l]!=bel[q[i-1].l])
{
d.reset();
l=br[bel[q[i].l]]+1;
r=l-1;
ret=sqs;
}
if(bel[q[i].l]==bel[q[i].r])
{
ll res=sqs;
for(ll j=q[i].l;j<=q[i].r;j++)
d2.join(b[j].u,b[j].v,res,1);
ans[q[i].id]=((res-sqs)%mod+mod)%mod;
for(ll j=q[i].l;j<=q[i].r;j++)
d2.cancel();
}
else
{
while(r<q[i].r)add_r(++r,ret);
ll tret=ret,tl=l;
while(l>q[i].l)add_l(--l,ret);
ans[q[i].id]=((ret-sqs)%mod+mod)%mod;//我是这样计算答案的
ret=tret;
while(l<tl)del_l(l++);
}
}
for(ll i=1;i<=m;i++)
printf("%lld\n",ans[i]*inv%mod);
return 0;
}
温馨提示，本代码思路正确，却只能通过洛谷 25 p t s \rm 25pts 25pts 的数据。