P1008 · OFFICIAL SOLUTION

P1008 商路照影官方题解

Gioush OJ · P1008 商路照影

商路照影

【题意简述】

给定一棵有根二叉树，第 $i$ 个节点的权值为 $w_i$ 。对于每个节点 $x$ ，统计满足 $u$ 在 $x$ 的左儿子子树内， $v$ 在 $x$ 的右儿子子树内，并且 $w_u<w_x<w_v$ 的有序点对 $(u,v)$ 数量。

显然，每一个合法点对的中转点 $x$ 都是唯一的。若记左儿子子树内权值小于 $w_x$ 的节点数量为 $L_x$ ，右儿子子树内权值大于 $w_x$ 的节点数量为 $R_x$ ，那么节点 $x$ 对答案的贡献就是 $L_xR_x$ 。

【数据点 1∼81\sim 81∼8】

这部分 $n\leq 2000$ 。

对于每个节点 $x$ ，分别遍历其左儿子子树与右儿子子树，统计权值小于和大于 $w_x$ 的节点数量即可，时间复杂度为 $\mathcal{O}(n^2)$ 。

【数据点 9∼129\sim 129∼12】

特殊性质保证二叉树按照编号自然连接，因此整棵树的高度为 $\mathcal{O}(\log n)$ 。

考虑对于每个节点维护其子树内所有权值组成的有序序列。得到两个儿子的序列以后，可以通过二分查询出 $L_x,R_x$ ，再使用归并排序的方法合并两个儿子的序列，并插入 $w_x$ 。

每个权值在树的每一层至多参与一次归并，总时间复杂度为 $\mathcal{O}(n\log n)$ 。

【正解一：按权值扫描】

首先对原树进行一次 DFS，求出每个节点的 DFN 序与子树大小。这样任意一个节点 $u$ 的子树都对应 DFN 序上的连续区间。

于是，求左儿子子树中权值小于 $w_x$ 的节点数量，可以转化为一个二维偏序问题：节点的 DFN 序需要落在一段区间中，权值需要小于给定值。

将所有节点按照权值从小到大排序，并使用树状数组维护已经加入节点的 DFN 序。处理节点 $x$ 时，树状数组中只保留权值小于 $w_x$ 的节点，那么在左儿子子树对应的 DFN 区间上查询区间和，得到的就是 $L_x$ 。

由于题目要求严格小于，所以相同权值的节点必须放在同一组中。对于一组权值相同的节点，应该先完成这一组的所有查询，再将这一组节点的 DFN 序加入树状数组。

同理，将所有节点按照权值从大到小处理，树状数组中只保留权值大于 $w_x$ 的节点，在右儿子子树对应的区间上查询即可得到 $R_x$ 。相同权值仍然需要先查询、后加入。

最后计算 $\sum_x L_xR_x$ 即可。

这是一种较自然的二维偏序维护方式：把权值这一维作为扫描顺序，把 DFN 这一维放进树状数组中维护。

排序的时间复杂度为 $\mathcal{O}(n\log n)$ ，树状数组操作的总时间复杂度为 $\mathcal{O}(n\log n)$ ，空间复杂度为 $\mathcal{O}(n)$ 。

【正解二：按 DFN 扫描】

也可以将二维偏序的两个维度交换。

我们仍然先 DFS 得到每个节点的 DFN。设节点 $x$ 的左儿子为 $l_x$ ，右儿子为 $r_x$ 。如果 $l_x$ 非空，那么 $l_x$ 子树在 DFN 序上对应一段区间

[\operatorname{MinD}(l_x),\operatorname{MaxD}(l_x)].

要求左儿子子树内权值小于 $w_x$ 的节点数量，即

\left|\{u:\operatorname{Dfn}(u)\in[\operatorname{MinD}(l_x),\operatorname{MaxD}(l_x)],\ w_u<w_x\}\right|.

将权值离散化后，严格小于 $w_x$ 等价于离散化权值不超过 $\operatorname{Rank}(w_x)-1$ 。于是可以把这次询问拆成两个前缀：

\operatorname{Ask}(\operatorname{MaxD}(l_x),\operatorname{Rank}(w_x)-1) - \operatorname{Ask}(\operatorname{MinD}(l_x)-1,\operatorname{Rank}(w_x)-1).

其中 $\operatorname{Ask}(p,v)$ 表示在 DFN 前缀 $[1,p]$ 中，权值排名不超过 $v$ 的节点数量。

右儿子子树内权值大于 $w_x$ 的节点数量同理。若总权值排名数为 $m$ ，则

\left|\{u:\operatorname{Dfn}(u)\leq p,\ w_u>w_x\}\right| =\operatorname{Ask}(p,m)-\operatorname{Ask}(p,\operatorname{Rank}(w_x)).

因此每个右儿子区间同样可以拆成两个 DFN 前缀。

具体实现时，将所有形如 $\operatorname{Ask}(p,v)$ 的询问按照 $p$ 从小到大排序。然后按 DFN 从小到大扫描节点，每扫到一个节点，就把它的权值排名加入树状数组。此时树状数组维护的是“当前 DFN 前缀中，各权值排名出现了多少次”。处理询问 $\operatorname{Ask}(p,v)$ 时，树状数组中恰好已经加入了 DFN 不超过 $p$ 的节点，查询权值前缀和即可。

代码中的 Q 结构体正是在记录这些前缀询问：

DFN 表示前缀右端点 $p$ ；
Value 表示权值阈值 $v$ ；
Times 表示区间差分中的 $+1$ 或 $-1$ ；
From=0 表示统计左儿子子树内的小于部分；
From=1 表示统计右儿子子树内的大于部分。

这一做法与正解一维护的是同一个二维偏序，只是扫描维度从权值换成了 DFN，树状数组中维护的维度也随之从 DFN 换成了权值。

时间复杂度仍为 $\mathcal{O}(n\log n)$ ，空间复杂度为 $\mathcal{O}(n)$ 。下面代码采用这种写法。

【参考代码】

1#include <cstdio>2#include <cstring>3#include <algorithm>4#define MAXN 2000105using namespace std;6 7int C[MAXN];8int lowbit(int x){return x&-x;}9int Query(int x) {10    int Ret=0;11    for (;x;x-=lowbit(x)) Ret+=C[x];12    return Ret;13}14void Modify(int x,int Val) {15    for (;x<MAXN;x+=lowbit(x)) C[x]+=Val;16    return ;17}18struct Q{19    int Value,DFN,Mark,From,Times;20}q[MAXN<<2];21bool cmp(Q a,Q b){return a.DFN<b.DFN;}22int n,MaxD[MAXN],MinD[MAXN],Size[MAXN][2],Val[MAXN],ls[MAXN],rs[MAXN],dfn[MAXN],Line[MAXN],Mapping[MAXN],Back[MAXN],cnt=0,cnd=0,cnq=0;23 24void Discrete() {25    sort(Line+1,Line+n+1);26    for (int i=1;i<=n;i++) {27        if (i==1||Line[i]!=Line[i-1]) Mapping[++cnt]=Line[i];28    }29    return;30}31 32int Find(int x) {return lower_bound(Mapping+1,Mapping+cnt+1,x)-Mapping;}33 34void DFS(int Now) {35    if (Now==0) return;36    dfn[Now]=++cnd;Back[cnd]=Now;37    DFS(ls[Now]);DFS(rs[Now]);38    MaxD[Now]=max(MaxD[ls[Now]],max(MaxD[rs[Now]],dfn[Now]));MinD[Now]=dfn[Now];39    if (ls[Now]) {40        q[++cnq]={Val[Now]-1,MaxD[ls[Now]],Now,0,1};41        q[++cnq]={Val[Now]-1,MinD[ls[Now]]-1,Now,0,-1};42    }43    if (rs[Now]) {44        q[++cnq]={Val[Now],MaxD[rs[Now]],Now,1,1};45        q[++cnq]={Val[Now],MinD[rs[Now]]-1,Now,1,-1};46    }47}48 49void Deal() {50    sort(q+1,q+cnq+1,cmp);51    int p=0;52    for (int i=1;i<=cnq;i++) {53        while (p<q[i].DFN) {54            p++;55            Modify(Val[Back[p]],1);56        }57        if (q[i].From==0) {58            Size[q[i].Mark][0]+=Query(q[i].Value)*q[i].Times;59        }60        else {61            Size[q[i].Mark][1]+=(Query(cnt)-Query(q[i].Value))*q[i].Times;62        }63    }64    return ;65}66 67int main() {68    freopen("trade.in","r",stdin);69    freopen("trade.out","w",stdout);70    memset(Size,0,sizeof(Size));71    scanf("%d",&n);72    for (int i=1;i<=n;i++) {73        scanf("%d",&Line[i]); Val[i]=Line[i];74    }75    Discrete();for (int i=1;i<=n;i++) Val[i]=Find(Val[i]);76    for (int i=1;i<=n;i++) {77        scanf("%d%d",&ls[i],&rs[i]);78    }79    DFS(1);80    Deal();long long Ans=0;81    for (int i=1;i<=n;i++) {82        Ans+=1ll*Size[i][0]*Size[i][1];83    }84    printf("%lld\n",Ans);85    return 0;86}