假设选中区间 $[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$ 升序排序，修改时用二分套线段树

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

线段树部分写得比较神奇

感觉网上的贪心题解都稍有问题？

单纯考虑一个树（不是基环树），发现可直接从子节点贪心得出父节点状态

首先，这是一个内向树森林

考虑一颗内向基环树 $T$，环上节点为 $s_1, s_2, \cdots,s_t$

对每一个环上节点和其子树分开执行贪心（这只是描述，实际上用拓扑排序递推）

1. 如果 $T$ 是一个环，则 $t/2$
2. 如果存在一个 $s_i$ 由贪心过程得出它可以投放，则环就会断成链
3. 如果不存在，则环还是完整的，$t/2$

贪心过程由拓扑排序执行，讨论 2 可以直接在这个过程中完成

仔细分析，考虑树上，若断一条树边 $(u, v)$，则会分成两个连通块

• 两个连通块之间有 $0$ 条附加边，则任意再切一条
• 两个连通块之间有 $1$ 条附加边，则只能切特定的一条
• 两个连通块之间有 $\geq 2$ 条附加边，无方案

如何快速计数？

记附加边为 $(x,y)$ ，发现 $(u, x),(v,y)$ 两条路径不相交则 $(x,y)$ 对 $(u,v)$ 有影响

即，附加边 $(x,y)$ 对于主要边树上 $(x,y)$ 路径上所有边都有影响

或者说，附加边 $(x,y)$ 会在树上产生环，如果切环上的边就必须把 $(x,y)$ 切掉

然后就是树上边差分

POJ 上 TLE 了，但是本地没问题，复杂度（应该）没挂？

容易发现，若不加新边，则总距离为 $2(n-1)$

发现 $k=1$ 时，连一条边等于环上的边只需走一次，显然最优连直径

发现 $k=2$ 时，再连一条边，若构成的环和第一次的环不相交，则可以直接减

若相交，则需要经过重叠部分两次，可以通过把边权改成 $-1$ 实现

对于新边能走一次，可以用，不实际在图上加边，来控制