51nod-1462 数据结构 解题报告

目录
  1. 1. 题意简述
  2. 2. 题目简析
  3. 3. 复杂度分析
  4. 4. Hint

*** 题目链接 ***
*** Code ***

题意简述

一棵 $N$ 个节点的树，以 1 为根。树上的每个节点有两个权值：$v_i$，$t_i$。初始时均为 0。
$Q$ 次操作：

  • 1 u d $\hskip .6em$ 对 $u$ 到根上所有点的 $v_i \text{+=} d$
  • 2 u d $\hskip .6em$ 对 $u$ 到根上所有点的 $t_i \text{+=} v_i \times d$

输出 $Q$ 次操作后所有节点的权值。

数据范围：$N,Q \leqslant 10^5$。
数据保证 64 位整数不会溢出。

题目简析

先考虑在一段区间中怎么维护这两个操作。

$t_i$ 增加值是 $v_i$ 和 $d$ 的乘积。

  • 当 $v_i$ 不发生改变，可以累加 $d$ 的值， $d’=\sum d$；
  • 当 $v_i$ 发生改变，$t_i \text{+=} v_i \times d’$，$d’=0$，$v_i \text{+=} d$。

由于我们求的是 $Q$ 次操作后每个节点的 $t_i$ 值；
维护一个类似 区间更新，单点求值 的问题即可。

操作一（$v_i$ 发生变化）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void Pushdown(int o, int lft, int rht) {
    t[o] += v[o] * d[o];
    if( lft < rht ) {
        d[lc] += d[o];
        d[rc] += d[o];
    }
    d[o] = 0;
}
int ul, ur, uv, uc;
void Update(int o, int lft, int rht) {
    Pushdown(o, lft, rht);
    if( ul <= lft && rht <= ur ) {
        v[o] += uv;
    } else {
        int mid = lft+rht >> 1;
        if( ul <= mid ) Update(lc, lft, mid);
        if( ur > mid ) Update(rc, mid+1, rht);
    }
}

操作二（$v_i$ 不发生变化）

1
2
3
4
5
6
7
8
9
10
11
12
void Update(int o, int lft, int rht, LL add) {
    if (ul <= lft && rht <= ur) {
        d[o] += uv;
        t[o] += add;
    }
    else {
        add += uv * v[o];
        int mid = lft + rht >> 1;
        if (ul <= mid) Update(lc, lft, mid, add);
        if (ur > mid) Update(rc, mid+1, rht, add);
    }
}

最后的 Query 操作只要把所有的标记 Pushdown 到叶子节点即可。
解决了区间的问题，剩下的只要树剖一下就好了。

复杂度分析

Update 操作是 $O(\log N)$ 的，执行 $Q$ 次；Query 操作是 $O(N)$ 的，但只执行一次。

  • 空间复杂度 $O(N)$
  • 时间复杂度 $O(Q\log N + N)$

Hint

数据范围比较大，会爆栈，需要手动扩栈。

1
#pragma comment(linker, "/STACK:102400000,102400000")

51nod 暂只有 Visual C++ 支持手动扩栈。

*** 树链剖分 ***