本文将介绍一种平衡树

复杂度我不会证

实现非常简单

首先发现 $k$ 很小，自然地想到 DP

令 $d$ 表示最短路

$f_{u, x}$ 代表从 $s$ 到 $u$ 路径长为 $d_u + x$ 的方案数量

称贝壳的种类为颜色

考虑离线做法，将询问按照 $r$ 升序排序

发现只需要维护每个颜色的目前最右出现位置（ $\le r$ ）

每个颜色只在最后出现的地方进行统计，显然可以保证最优（因为离线）

举个例子

1
2
3
4
5
6
7
8
9
10
11
12
13

颜色序列为
1 3 1 2 1

扫到 1 （位置）
1 0 0 0 0
扫到 2
1 1 0 0 0
扫到 3
0 1 1 0 0
扫到 4
0 1 1 1 0
扫到 5
0 1 0 1 1

0/1 序列用树状数组维护即可，答案即是 0/1 序列 $sum(l, r)$

在线做法，用可持久化线段树即可

假设选中区间 $[l, r]$，经过题目中的操作，获得的和为该区间的得分，其中最小的成为最小得分 $f_{l,r}$

显然得选满 $d$ 长度

所以对于区间 $[l, r]$ 只需要知道其中长度为 $d$ 的最大子段和就可以知道区间的最小得分

当然是用线段树维护啦

学数据结构果然会变傻

发现可以用单调队列维护最大子段和

然后发现若是区间 $f_{l, r} > p$ 则必然有 $\forall~x<l,y>r~~~f_{x, y} > p$

然后就是一道 two-pointer 的题了

带修改最大子段和查询

考虑维护一棵线段树，节点 $[l, r]$ 记录

• 最大子段和 $m$
• $l$ 开始的最大子段和 $el$
• $r$ 结尾的最大子段和 $er$

可以非常方便地合并

然后考虑查询区间 $[L, R]$，当前节点为 $[l, r]$ ，保证 $[l,r]\cap[L,R]\neq \varnothing$

1. $[l, r]\subseteq [L, R]$ 返回 (el, er) ，更新 ans
2. $r \le mid$ 返回 q(ls)
3. $l > mid$ 返回 q(rs)
4. $l \le mid < r$ 返回合并结果，更新 ans

一开始觉得 $2\ 3\ 4$ 这么做不太严谨，但其实是可以保证正确性的

因为若 $el$ 或 $rl$ 不在 $[L, R]$ 时，它们也不会再被用作更新 ans，反证法可证

因为 $a_i\le 10^{12}$ 所以发现开非常少次数的根号就会到达 $1$，使答案不再改变

于是考虑对 $[L,R]$ 区间开根时，若 $\max a_i \le 1$ 就不用操作了

通过在递归过程中判断实现

所以线段树维护区间和与区间最大

辣鸡 BZOJ 评测机，笔记本都只要跑 300ms，在你的老爷 CPU 上直接 TLE

这是一道树形 DP

首先是状态设计，由于用户人数相比耗费作为数组维度比较简单，所以这样设计

$f$[节点编号][用户数] = 最大利润（ 可以 $<0$ ）

考虑节点 $u$，如何从子节点 $v$ 得到

把子节点的状态看成一种物品，就是分组背包了

外层倒序枚举 $u$ 的用户（状态），内层枚举 $v$ 人数（看成背包中的物品）

1
2
3
4
5

per(i, s, 1)
    rep(j, 1, t){
        if (i - j < 0) break;
        f[u][i] = max(f[u][i], f[u][i-j] + f[v][j] + w)
    }

复杂度不知道怎么证

观察

发现一个绝对值在外，一个绝对值在里

类似的

只要令

就可满足

例如 $n=6,k=2$ 时

1 3 12 11 10 9 8 7 6 5 4 2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

#include <iostream>
#define rep(i, l, r) for (int i = (l); i <= (r); ++i)
#define per(i, l, r) for (int i = (l); i >= (r); --i)
using std::cin;
using std::cout;
int main() {
#ifdef LOCAL
    freopen("input", "r", stdin);
#endif
    std::ios::sync_with_stdio(false);
    cout.tie(0);
    int n, k;
    cin >> n >> k;
    if (k == 0) {
        per(i, 2 * n, 1) cout << i << ' ';
        return 0;
    }
    cout << 1 << ' ' << k + 1 << ' ';
    per(i, 2 * n, 2) {
        if (i == k + 1) continue;
        cout << i << ' ';
    }
    return 0;
}

尽量充分利用状态，降低复杂度，另外一道题

状态设计比较巧妙

$F$[ 剩余空间 ][ 辩方总分 - 控方总分 ] = 辩方总分 + 控方总分

跑一个背包

$F[v+1, x + a_i - b_i] = \max\{F[v, x] + a_i + b_i, F[v+1, x + a_i - b_i]\}$

找方案比较麻烦，如果直接记由哪个状态转移来是不行的，因为后续更新会破坏

所以要搞一个类似链表的东西

这是一个贪心+线段树的解法，复杂度是 $O(n\log^2 n)$

把要求按 $b$ 升序排序，修改时用二分套线段树

其他题解怎么都是一个一个跳的，复杂度不会挂吗？

线段树部分写得比较神奇