（回滚莫队）洛谷 P10268 符卡对决 题解

居然还没调出来？感觉是数据类型的问题，真是吓人。先把思路写一下吧。

题意

灵梦一共有 $n$ 张符卡，每张卡都有一个能力值，对于第 $i$ 张卡，它的能力值为 $a_i$，现在她想从中选出两张符卡并使用它们，灵梦发现，如果她同时打出了两张符卡 $i,j$，这两张符卡造成的伤害将会是 $a_i\times a_j$。

这些符卡之间有能力的冲突，灵梦会告诉你这些符卡的兼容性，具体而言这些符卡之间有 $m$ 条关系，这些关系表明某两张符卡之间是兼容的，注意，如果符卡 $i,j$ 兼容且符卡 $j,k$ 兼容，那么符卡 $i,k$ 也是兼容的，如果打出的两张符卡之间不是兼容的，那么它们造成的伤害为 $0$。

她很好奇符卡之间的兼容性会造成什么样的影响，所以她会询问你 $q$ 次，每次告诉你一对正整数 $l,r$，意味着只有编号在区间 $[l,r]$ 内的关系才会生效。

灵梦不想把魔理沙虐得太惨，所以她会随机从所有符卡中选出两张不同的符卡来打出，她想知道每次询问造成的伤害的期望值对 $10^9+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,2)$，那么它们不兼容，伤害值为 $0$，这种情况的概率是 $\frac{1}{6}$。

如果选择的符卡是 $(1,3)$，那么它们不兼容，伤害值为 $0$，这种情况的概率是 $\frac{1}{6}$。

如果选择的符卡是 $(1,4)$，它们兼容，伤害值为 $a_1\times a_4=35$，这种情况的概率是 $\frac{1}{6}$。

如果选择的符卡是 $(2,3)$，它们兼容，伤害值为 $a_2\times a_3=16$，这种情况的概率是 $\frac{1}{6}$。

如果选择的符卡是 $(2,4)$，那么它们不兼容，伤害值为 $0$，这种情况的概率是 $\frac{1}{6}$。

以此类推，最终的期望值是 $\frac{17}{2}$，其在模 $10^9+7$ 意义下等于 $500000012$。

$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$。

思路

给定询问区间，说编号在 $[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\sim br$ 和 $br+1\sim r$，右区间部分永久化，左区间部分回滚……这就是回滚莫队的套路了，可以前往上一篇文章粗略学习。

题目要求造成的伤害的期望值对 $10^9+7$ 取模后是多少，拆掉期望就是 $E=\frac{ans}{\frac{n(n-1)}{2}}$，$ans$ 为当前询问造成的最大伤害。

计算 $ans$ 就是妥妥的数学题了。我们假设一组连通块内有 $a,b,c,d$，答案就是 $ab+bc+cd+da$，但是这样不好在并查集合并时直接查询，考虑式子变形：
$$=\frac{1}{2}(2ab+2ac+2ad+2bc+2bd+2cd)$$

$$=\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)]$$

$$=\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)]$$

$$=\frac{1}{2}[(a+b+c+d{)}^2-(a^2+b^2+c^2+d^2)]$$

即连通块内战斗力总和的平方，减去各符卡平方的和，再除以 $2$。

各符卡平方的和在计算答案数组时，再统一减去，可以先把动态答案 $ret$ 的初值修改为 $\sum _{i=1}^n{a}_i^2$，计算答案时方便得到相反数。

具体细节见代码：

代码

#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;
}

温馨提示，本代码思路正确，却只能通过洛谷 $25pts$ 的数据。