日记

你甘心停留在 C 组吗？

T2 # Link to T2

我们发现 $m \le 1 \times 10^6$，这个 $q$ 我们直接不管他，我们预处理 $ans_i$ 表示询问 $i$ 时的答案，到时候直接 $O(1)$ 查询就是了。

考虑如何求 $ans_i$。发现对于每个 $i$，如果独立的求显然不好做。考虑如何从 $ans_{i - 1}$ 递推。我们发现这是一个神经的倍增。而上面的那一半和下面的那一半跳的步数是一样的。考虑求上面的那一半然后乘 $2$。

如何求上面那一半呢？考虑何时 $p$ 会继续往下跳。发现，会造成影响的只有 $a_1,a_3,a_5,\dots,a_{2^n - 1}$，因为只跳的到这些位置。显然只有 $O(\log_2 n)$ 个位置。我们直接枚举当前跳到了 $a_p$。何时它会继续往下跳，并造成 $2$ 的贡献？（这里的贡献按 $2$ 算了就不用执行上文的乘 $2$ 了）

发现当且仅当 $a_p \le i$ 的时候会继续往下跳并造成贡献。$a_p \in [1,i - 1]$ 的我们已经在 $ans_{i - 1}$ 里算过了，所以我们只考虑 $a_p = i$。那么这个位置会造成的贡献就是 $\binom{i - 1}{p - 1} \times \binom{m - i}{n - p} \times 2$。具体来说，因为 $a$ 是单调递增的，所以我们要把 $i - 1$ 个数取 $p - 1$ 个填进 $[1,p - 1]$ 这个范围内。后面同理。最后乘上一个 $2$ 作为贡献，就可以加进 $ans_i$ 了。

T3 # Link to T3

我不想也不能。

这是一个无根树。考虑如果有根（也就是有一个固定的终点怎么做）。我们发现可以做 dp。对于每个节点 $u$ 记录一个 $a_u$，里面存两个数，分别是到达 $u$ 的最快的选手和他所用的时间。转移是平凡的。

考虑没有一个固定的根怎么办。对于一个无根树，我们就可以做换根 dp。考虑如和 $O(1)$ 换根。我们只用在 $a_u$ 里多记录几个值。分别是：第一个到达的与他的时间，第二个到达的与他的时间，第一个从哪里来。如何换根呢？我们考虑从 $u$ 转移 $v$（$v \in son_u$）。我们发现：如果最快的不来自 $v$，我们就直接拿他来转移 $v$，反之就拿次快的转移 $v$。大力分讨即可。统计答案就离线，然后换根换到 $t$ 的时候把每个 $s$ 对应的得分记录一下就行。

别忘了还原。

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

void dfs2(int u,int fa)
{
    for (auto [s,id] : que[u])
        ans[id] = buc[s];// 桶记录得分
    for (auto [v,w] : g[u])
    {
        if (v == fa)
            continue;
        Klee tu = a[u],tv = a[v];
        buc[a[u].fir.second]--,buc[a[v].fir.second]--;
        if (a[u].from == v)// 如果来自 v 就换成次快的
            a[u].fir = a[u].sec;
        pii tmp = a[u].fir;
        tmp.first += w;
        if (tmp < a[v].fir)// 转移
        {
            a[v].sec = a[v].fir;
            a[v].fir = tmp;
            a[v].from = u;
        }
        else if (tmp < a[v].sec)
            a[v].sec = tmp;
        buc[a[u].fir.second]++,buc[a[v].fir.second]++;
        dfs2(v,u);
        // 别忘了还原
        buc[a[u].fir.second]--,buc[a[v].fir.second]--;
        buc[tu.fir.second]++,buc[tv.fir.second]++;
        a[u] = tu,a[v] = tv;
    }
}

Election Queries G# Link to

题读错了 + 码力太强。

具体就是：结论：设 $v_i$ 表示 $i$ 所获得的总票数。那么有结论：$x,y$ 能够当选，当且仅当 $v_x + v_y \ge vmax$，$vmax$ 表示 $v$ 的最大值。用 map 维护 $v$ 里出现的值。set 维护每个值出现的位置。因为 $v$ 只有 $O(\sqrt{n})$ 种取值，所以每次直接枚举每个出现次数不为 $0$ 的每个值，然后双指针找出最大的 $|x - y|$ 使得 $v_x + v_y \ge vmax$。

The Best Subsequence G# Link to

$n \le 1 \times 10^9$，对于反转操作直接动开线段树。

考虑如何查询 $[l,r]$ 区间内的最大字典序子序列。显然是找到一个最右的 $pos$ 使得 $cnt_{l,cnt} + r - cnt \ge k$。$cnt_{l,cnt}$ 表示 $[l,pos]$ 内的 $1$ 的个数。这么做的原因是在前面尽量的取到更多更长的 $1$。二分找到最右的 $pos$，维护“将其解释为二进制数时的值”线段树上维护即可。

后日谈 # Link to 后日谈

明天继续。

A 掉 T1 就是赢。但是也别因为没切掉 T1 就摆烂。无论怎样都把暴力打完。