题解 【P7570 「MCOI-05」多宇】
command_block
2021-10-21 10:40:35
**题意** : 给出一棵 $n$ 个点的外向树 $T$,以及 $m$ 条额外的边,满足加入这些边之后图 $G$ 是 DAG。
对于点对 $u,v$ ,若在 $T$ 中 $u$ 不能到达 $v$ ,但是在 $G$ 中 $u$ 可以到达 $v$ ,则称点对 $(u,v)$ 是好的。
每次询问给出 $l,r$ ,求有多少对好的 $(u,v)$ 满足 $l\leq u<v\leq r$ 。
$n\leq 7\times 10^5,q\leq 3\times 10^5,m\leq 100$ ,时限$\texttt{5s}$。
------------
> @newbiewzs 题解的详细版。
对于额外边 $u\rightarrow v$ ,将 $v$ 标记为“**关键点**”。记关键点集合为 $E$ 。
观察好对子 $(a,b)$ 的分布。
在固定 $a$ 时,若 $(a,b)$ 是好的,且 $T:b\leadsto c$ ,则 $(a,c)$ 是好的。
这说明 $b$ 的分布必然是若干不交的 $T$ 的子树(称作**好子树**)。不难进一步发现,这些子树的根都是关键点。
------------
对于每个好的对子 $(a,b)$ ,在所有可能的路径 $G:a\leadsto b$ 中,都必然有至少一个关键点。取某个关键点作为“统计点”,这样我们才能对贡献转置。
根据如上观察,我们取 $b$ 所在“好子树”的根作为**统计点** $v$ ,这样是唯一的。
考虑如何判定 $(a,b)$ 是否满足“是好的,且统计点为 $v$”。
首先有必要条件 $T:a\not\leadsto b$ ,否则 $(a,b)$ 不是好的。
然后,为了保证统计点,一个显然的必要条件是,$G:a\leadsto v$ 且 $T:v\leadsto b$ 。但这不充分,我们称满足该条件的 $v$ 为 $(a,b)$ 的**中转点**。
不难发现,中转点都是 $T$ 中 $b$ 的祖先,那么深度最小(是其他中转点的祖先)的中转点就是统计点了。
对关键点 $v$ ,记 $S_v=\{u\ \big|\ T:v\leadsto u\}$ , $T_v=\{u\ \big|\ G:u\leadsto v,\text{不存在}v'\text{使得}G:u\leadsto v',T:v'\leadsto v\}$ 。
那么 $a\in T_v,b\in S_v$ 就是“统计点为 $v$”的充要条件。
再将 $T:a\not\leadsto b$ 纳入考虑,注意到 $T:v\leadsto b,G:v\not\leadsto a$ ,前者可以等价为 $T:a\not\leadsto v$ 。
于是改记 $T_v=\{u\ \big|\ G:u\leadsto v,T:u\not\leadsto v,\text{不存在}v'\text{使得}G:u\leadsto v',T:v'\leadsto v\}$ 。
------------
考虑如何求 $S,T$ ,使用转置。
记 $S'_u=\{v\in E\ \big|\ T:v\rightarrow u\}$ , $T'_u=\{v\in E\ \big|\ G:u\leadsto v,T:u\not\leadsto v,\text{不存在}v'\text{使得}G:u\leadsto v',T:v'\leadsto v\}$ 。
显然,$S',T'$ 与 $S,T$ 互为转置。
$S'$ 是简单的传递闭包。
对于 $T'$ ,先用传递闭包处理 “$u\leadsto v$” ,然后用 dfs 序和树形 DP 处理 “$T:u\not\leadsto v$” 和 “$\text{不存在}v'\text{使得}G:u\leadsto v',T:v'\leadsto v$”。
使用 `bitset` ,时间 $O(nm)$ ,空间 $O(nm/w)$ 。
- 卡常技巧
- 不要用 `[]` 操作 `bitset` ,而要使用 `set,reset,test` 等函数,常数小很多。
- 树形 DP 可以转为 dfs 序上的问题。
------------
接下来考虑如何回答询问。
为了方便处理,将条件 $[l\leq a<b\leq r]$ 拆成 $[l\leq b\leq r][a<b]-[l\leq b\leq r][a<l]$ 。
$$
\begin{aligned}
{\rm Ans_1}&=\sum\limits_{v\text{是关键点}}\sum\limits_{(a,b)}[l\leq b\leq r][a<b][(a,b)\text{是好的,统计点是}v]\\
&=\sum\limits_{v\text{是关键点}}\sum\limits_{(a,b)}[l\leq b\leq r][a<b][a\in T_v][b\in S_v]\\
&=\sum\limits_{v\text{是关键点}}\sum\limits_{l\leq b\leq r}[b\in S_v]\sum\limits_{a<b}[a\in T_v]\\
\end{aligned}
$$
$$
\begin{aligned}
{\rm Ans_2}&=\sum\limits_{v\text{是关键点}}\sum\limits_{(a,b)}[l\leq b\leq r][a<l][(a,b)\text{是好的,统计点是}v]\\
&=\sum\limits_{v\text{是关键点}}\sum\limits_{(a,b)}[l\leq b\leq r][a<l][a\in T_v][b\in S_v]\\
&=\sum\limits_{v\text{是关键点}}\Bigg(\sum\limits_{l\leq b\leq r}[b\in S_v]\Bigg)\Bigg(\sum\limits_{a<l}[a\in T_v]\Bigg)\\
\end{aligned}
$$
对于每个 $v$ ,上述式子都容易用前缀和搞定。
总时间复杂度 $O((n+q)m)$ ,空间复杂度(若离线) $O(nm/\omega+q)$。
```cpp
#include<algorithm>
#include<cstdio>
#include<vector>
#include<bitset>
#define ll long long
#define pb push_back
#define MaxN 700500
#define MaxQ 300500
#define MaxM 105
using namespace std;
struct Line{int t,nxt;}g[MaxN];
int fir[MaxN],tl;
void adl(int u,int v)
{g[++tl]=(Line){v,fir[u]};fir[u]=tl;}
int dfn[MaxN],out[MaxN],tp[MaxN],tim;
void dfsT(int u)
{
tp[dfn[u]=++tim]=u;
for (int i=fir[u];i;i=g[i].nxt)
dfsT(g[i].t);
out[u]=tim;
}
bitset<MaxM> T0[MaxN];
int id[MaxN],st[MaxM],tn;
bool vis[MaxN];
void dfsG(int u)
{
if (id[u])T0[u][id[u]]=1;
vis[u]=1;
for (int i=fir[u];i;i=g[i].nxt){
if (!vis[g[i].t])dfsG(g[i].t);
T0[u]|=T0[g[i].t];
}
}
int n,m,q,S[MaxN],T[MaxN],r[MaxM];
ll O[MaxN],ans[MaxQ];
int ql[MaxQ],qr[MaxQ];
int main()
{
scanf("%d%d",&n,&m);
for (int i=2,fa;i<=n;i++)
{scanf("%d",&fa);adl(fa,i);}
dfsT(1);
for (int i=1,u,v;i<=m;i++){
scanf("%d%d",&u,&v);
adl(u,v);id[v]=1;
}
for (int i=1;i<=n;i++)if (id[tp[i]])
{st[++tn]=tp[i];id[tp[i]]=tn;}
for (int i=1;i<=tn;i++){
r[i]=i;
while(r[i]<tn&&dfn[st[r[i]+1]]<=out[st[i]])r[i]++;
}
dfsG(1);
for (int u=1;u<=n;u++)
for (int k=1;k<=tn;k++)
if (T0[u].test(k)){
int lim=r[k];
while(k+1<=lim)T0[u].reset(++k);
}
scanf("%d",&q);
for (int i=1;i<=q;i++)
scanf("%d%d",&ql[i],&qr[i]);
for (int k=1;k<=tn;k++){
int v=st[k];
for (int u=1;u<=n;u++){
S[u]=(dfn[v]<=dfn[u]&&dfn[u]<=out[v]);
T[u]=T0[u].test(k)&&!(dfn[u]<=dfn[v]&&dfn[v]<=out[u]);
O[u]=O[u-1]+S[u]*T[u-1];
T[u]+=T[u-1];S[u]+=S[u-1];
}
for (int i=1;i<=q;i++){
int l=ql[i],r=qr[i];
ans[i]+=O[r]-O[l-1]-1ll*(S[r]-S[l-1])*T[l-1];
}
}
for (int i=1;i<=q;i++)
printf("%lld\n",ans[i]);
return 0;
}
```