题目理解

我们有一个初始没有边的 $N$ 个节点的树（最终会建成），节点 $1$ 为首都，每个节点 $i$ 有一个活跃度 $C_i$。我们需要按顺序执行 $N-1$ 次加边操作，每次操作 $(A_j, B_j)$ 满足：

• 当前 $A_j$ 与 $1$ 连通，$B_j$ 与 $1$ 不连通
• 在 $A_j$ 到 $1$ 的路径上，统计满足 $s$ 在 $t$ 之前且 $C_s > C_t$ 的有序对 $(s,t)$ 数量
• 将该路径上所有节点的活跃度改为 $C_{B_j}$

我们需要对每次操作输出统计的数量。

问题分析

1. 操作性质

• 每次操作实际上是将一个未连通的节点 $B_j$ 连接到已连通的节点 $A_j$ 上
• 最终构建的是一棵以 $1$ 为根的有根树
• 每次查询的是根到 $A_j$ 路径上的逆序对数量

2. 关键难点

• 动态修改路径上的活跃度
• 高效统计路径上的逆序对数量
• 处理 $N \leq 10^5$ 的大数据规模

算法思路

1. 离散化处理

由于活跃度范围很大 ($1 \le C_i \le 10^9$)，首先进行离散化：

for (int i = 1; i <= n; ++i)
    read(a[i]), t[i] = a[i];
std::sort(t + 1, t + n + 1);
int pos = std::unique(t + 1, t + n + 1) - t - 1;
for (int i = 1; i <= n; ++i)
    a[i] = std::lower_bound(t + 1, t + pos + 1, a[i]) - t;

2. LCT (Link-Cut Tree) 维护

使用 LCT 来维护树的连通性和路径信息：

数据结构定义

int ch[N][2], fa[N], v[N], tag[N], siz[N];

• ch[u][0/1]: 左右儿子
• fa[u]: 父节点
• v[u]: 节点当前活跃度（离散化后）
• tag[u]: 懒标记，用于路径赋值
• siz[u]: 子树大小

核心操作：Access

ll access(int x, int C) {
    ll ans = 0;
    int y = 0, last = 0;
    std::vector<int> vec;
    
    for (y = 0; x; x = fa[y = x]) {
        splay(x), ch[x][1] = y, pushup(x);
        ans += 1LL * (siz[x] - last) * ask(v[x] - 1);
        add(v[x], siz[x] - last), vec.pb(v[x]), last = siz[x];
    }
    upd(y, C);
    for (auto it : vec) clear(it);
    return ans;
}

3. 树状数组统计逆序对

使用树状数组来统计当前路径上的逆序对：

int c[N];
void add(int x, int C) {
    for (; x < N; x += lowbit(x)) c[x] += C;
}
int ask(int x) {
    int ans = 0;
    for (; x; x -= lowbit(x)) ans += c[x];
    return ans;
}

算法流程

1. 初始化

• 离散化活跃度
• 初始化节点1的信息

2. 处理每次操作

对于操作 $(A_j, B_j)$：

1. 执行 access(A_j, a[B_j]) 操作
2. 在access过程中：
   • 将路径上的节点splay到根
   • 用树状数组统计当前节点的贡献
   • 更新路径上的活跃度

3. 连接新节点

将 $B_j$ 连接到 $A_j$，完成树的构建

核心算法原理

Access操作详解

在LCT的access过程中：

• 从 $A_j$ 不断向上走到根
• 对于每个节点 $x$，统计其右子树中活跃度小于 $v[x]$ 的节点数量
• 公式：ans += (siz[x] - last) * ask(v[x] - 1)
  • siz[x] - last: 当前节点新增的子树大小
  • ask(v[x] - 1): 当前路径上活跃度小于 $v[x]$ 的节点数

时间复杂度

• 离散化: $O(N \log N)$
• 每次Access: $O(\log^2 N)$（树状数组 + LCT）
• 总复杂度: $O(N \log^2 N)$

代码亮点

1. 离散化优化: 将大范围值映射到小范围，便于树状数组处理
2. LCT维护: 动态维护树结构，支持路径操作
3. 树状数组统计: 高效统计逆序对数量
4. 懒标记传播: 支持路径上的批量赋值操作

算法标签

• 数据结构: LCT (Link-Cut Tree)、树状数组
• 离散化: 处理大范围数值
• 树结构: 动态树维护
• 逆序对统计: 组合计数问题

总结

这道题通过巧妙的LCT和树状数组结合，解决了动态树路径上的逆序对统计问题。算法充分利用了LCT的路径操作特性和树状数组的高效统计能力，在 $O(N \log^2 N)$ 时间内完成了所有查询，是数据结构综合应用的典型范例。