P1071 · OFFICIAL SOLUTION

P1071 风铃九重错响官方题解

Gioush OJ · P1071 风铃九重错响

【部分分：测试点 1∼41\sim 41∼4】

装置有 $n-1$ 根横杆，每根横杆都有回旋与不回旋两种选择。枚举全部 $2^{n-1}$ 种选择后，递归得到最终音牌序列。
对每个序列枚举所有位置对统计错响，时间复杂度为 $\mathcal O(2^{n-1}n^2)$ 。
横杆回旋只会改变左右两座子装置的先后关系，不会改变它们各自内部已经产生的错响。这是后续拆分贡献的依据。

【部分分：测试点 5∼95\sim 95∼9】

对每座子装置保存其中全部音牌值排好序后的序列。处理一根横杆时，用双指针统计左侧音牌大于右侧音牌的二元组数量。
设左右音牌数分别为 $x,y$ ，保持原方向产生 $u$ 次跨侧错响。由于音牌值互不相同，回旋后产生的跨侧错响恰好为 $xy-u$ 。
当前横杆贡献 $\min(u,xy-u)$ ，随后归并两个有序序列。最坏时间复杂度为 $\mathcal O(n^2)$ 。

【部分分：测试点 10∼1410\sim 1410∼14】

特殊性质保证每根横杆至少有一侧直接悬挂一枚音牌，因此装置可以看成逐次向已有序列加入一个新值。
用树状数组维护已经出现的音牌值。加入 $a$ 时，前缀和给出已有值中小于 $a$ 的数量，总数减去前缀和便得到大于 $a$ 的数量。
两个数量分别对应新音牌放在左侧与右侧时的跨侧错响。取较小值加入答案，时间复杂度为 $\mathcal O(n\log n)$ 。

【部分分：测试点 15∼1915\sim 1915∼19】

这一档只有 $n\leq2\times10^3$ ，继续使用第二档的有序序列归并即可。
每个结点都能独立取 $\min(u,xy-u)$ ，说明动态规划本身已经完成。平方复杂度只来自反复扫描并复制子树中的音牌值。
正解需要让所有子树共享同一套值域结构，并在合并结构的同时统计跨侧错响。

【正解】

为每个子装置建立一棵值域线段树。叶子 $v$ 记录这座子装置中值为 $v$ 的音牌数量，每个内部结点记录对应值域中的音牌总数。
合并左树 $X$ 与右树 $Y$ 时，当前值域中 $X$ 的右半部分都大于 $Y$ 的左半部分，所以产生

\operatorname{Count}(X_R)\operatorname{Count}(Y_L)

次跨侧错响。随后递归合并两侧相同值域。

递归得到的总和就是保持方向时的 $u$ 。当前横杆答案仍然加入 $\min(u,xy-u)$ 。
定义 $F_u$ 表示以结点 $u$ 为根的装置内部最少错响数。叶子的边界为 $F_u=0$ 。
若横杆 $u$ 的左右儿子为 $l,r$ ，跨侧错响为 $v$ ，左右音牌数为 $x,y$ ，完整转移为

F_u=F_l+F_r+\min(v,xy-v).

输入保证儿子编号小于父亲编号，所以按照编号递增处理时，两个儿子的值域树与答案都已经计算完成，不需要再进行递归遍历。
每枚音牌最初只在根到叶的一条值域路径上建立结点，合并时直接复用已有结点，不复制整棵树。
每层值域中，一个结点只会被并入更大的子装置一次，总时间复杂度为 $\mathcal O(n\log n)$ ，空间复杂度为 $\mathcal O(n\log n)$ 。
错响数量最大为 $\binom n2$ ，答案与合并时的乘积都必须使用 long long。每组数据开始前要重置结点计数器与空结点。

【参考代码】

1/*2Author:Ehundategh3Date:2026/8/194Name:chime.cpp5You steal,I kill.6*/7#include <cstdio>8#include <cstring>9#include <algorithm>10#define MAXN 40001011#define MAXM 420001012using namespace std;13 14int c,T,n,cnt=0,Line[MAXN],ls[MAXN],rs[MAXN],Root[MAXN];15long long Ans[MAXN];16 17struct node{18    int ls,rs,Count;19}Node[MAXM];20 21int Insert(int l,int r,int Pos) {22    int Now=++cnt;23    Node[Now]={0,0,1};24    if (l==r) return Now;25    int Mid=(l+r)>>1;26    if (Pos<=Mid) Node[Now].ls=Insert(l,Mid,Pos);27    else Node[Now].rs=Insert(Mid+1,r,Pos);28    return Now;29}30 31int Merge(int x,int y,int l,int r,long long &Ret) {32    if (!x||!y) return x+y;33    if (l==r) {34        Node[x].Count+=Node[y].Count;35        return x;36    }37    Ret+=1ll*Node[Node[x].rs].Count*Node[Node[y].ls].Count;38    int Mid=(l+r)>>1;39    Node[x].ls=Merge(Node[x].ls,Node[y].ls,l,Mid,Ret);40    Node[x].rs=Merge(Node[x].rs,Node[y].rs,Mid+1,r,Ret);41    Node[x].Count=Node[Node[x].ls].Count+Node[Node[x].rs].Count;42    return x;43}44 45void Solve() {46    scanf("%d",&n);47    cnt=0;Node[0]={0,0,0};48    for (int i=1;i<=n;i++) scanf("%d",&Line[i]);49    for (int i=n+1;i<=2*n-1;i++) scanf("%d%d",&ls[i],&rs[i]);50    for (int i=1;i<=n;i++) {51        Root[i]=Insert(1,n,Line[i]);52        Ans[i]=0;53    }54    for (int i=n+1;i<=2*n-1;i++) {55        long long Ret=0;56        long long Left=Node[Root[ls[i]]].Count,Right=Node[Root[rs[i]]].Count;57        Root[i]=Merge(Root[ls[i]],Root[rs[i]],1,n,Ret);58        Ans[i]=Ans[ls[i]]+Ans[rs[i]]+min(Ret,Left*Right-Ret);59    }60    printf("%lld\n",Ans[2*n-1]);61    return;62}63 64int main() {65    scanf("%d%d",&c,&T);66    while (T-->0) Solve();67    return 0;68}