JGELR #1 非官方营业日志

A1. 遐想碧空无边

题意：

$10^5$ $50000$ 个操作。
L R K $[L,R]$ $K=1$ $K=0$ 为降序。
最后输出最终的字符串。

题解：

$26$ $26\log_2{n}$ 执行区间推平操作即可。

B1. 即使暴雨倾泻

题意：

$p$ $f(p)$ $g_i$ $p_1, p_2, \cdots, p_i$ $f(p)$ $g_1,g_2,\cdots,g_n$ 中不同的数的个数。
$f_{max}(n)$ $1,2,\cdots,n$ $p$ $f(p)$ $1,2,\cdots,n$ $p$ $f(p)=f_{max}(n)$ $10^9+7$ $n\le 10^6$ 。

题解：

$p$ $h\left(\prod p_i^{b_i}\right)=\sum b_i$ $f_{max}(n)=\max_{i=1}^nh(i)$ $n$ $n\in [2^k,2^{k+1})$ 。

$n<3\cdot 2^k$ $h$ $2^k$ $2$ $O(n\log_2{n}+\log_2(n))$ 。

$n\ge 3\cdot 2^k$ $h$ $3\cdot 2^k$ $3$ $O(n\log_2{n}+\log_2^2(n))$ 。

C1. 锈迹斑斑的梦

题面：

$n$ $1$ $n$ $i$ $a_i,b_i$ 。
$x$ $y$ $a_x\times b_y$ 。跳跃多次走过一条路径的总费用为每次跳跃的费用之和。请分别计算出每个节点到达树的每个叶子节点的费用中的最小值。
$1$ ，根节点也不算做叶子节点。另外，不能从一个节点跳到它自己.
$2\leq n\leq 10^5$ $-10^5\leq a_i\leq 10^5$ $-10^5\leq b_i\leq 10^5$ 。

题解：

$a=x$ $u$ $x$ $O(n\log n)$ $O(n\log n)$ 的了。

D1. 已不愿再沉眠

题意：

$S$ 。当且仅当满足以下条件时该组正整数成立：
$S \subseteq \{1,2,...,n\}$
$a \in s$ $b \in s$ $|a - b| \not ={x}$ $|a - b| \not ={y}$
$n,x,y$ $(1 \leq n \leq 10 ^ 9; 1 \leq x, y \leq 22)$ 。

题解：

$x+y$ 的周期不断循环形成的（感性理解一下，好像确实吧）。

$x+y$ $S$ $S$ $y$ $x$ $S$ 合法矛盾）。

$x+y$ $S$ $\le n\bmod x+y$ 的数最多。

$x\perp y$ $pos$ $pos-y$ $pos+y$ $x$ $+y$ $O(x+y)$ $f(n,x,y)$ 。

$x\not\perp y$ $d=\gcd(x,y)$ ，我们分成两类讨论，仔细思考一下发现：

ans(n,x,y)=(n\bmod d)\cdot f\left(\left\lfloor\frac nd\right\rfloor+1,\frac xd,\frac yd\right)+(d-(n\bmod d))\cdot f\left(\left\lfloor\frac nd\right\rfloor,\frac xd,\frac yd\right)

A2. 水果

题面：

$n$ $f$ ，求出：
$\sum_{l=1}^{n}\sum_{r=l}^{n} f(l,r)$
$f(l,r)$ $f[l,r]$ $n\le 5 \times 10^5$ 。

题解：

$O(n)$ $s_i=\sum_{l=1}^i f(l,i)$ $f_i=0$ $s_i=s_{i-1}$ $s_i=s_{i-1}+i-pre$ $pre$ 表示上一处这么多的连续一是在哪个位置。（当然，聪明的你也可能直接用了吉老师线段树维护了这个东西 /fn）。

B2. 金币

题面：

$1\times n$ $m$ $m$ $m$ 个格子中），则被判定为输家。已经知道 Alice 和 Bob 都是极致聪明的人，他们在任何局面下总能做出最优的操作。那么有多少初始状态能保证 Alice 必胜呢？
$n\le 1.5\times 10^5,m\le 50$ 。

题解：

首先这个等价于一个阶梯 Nim 问题：

阶梯 Nim 问题：有一个楼梯，每个台阶上放了一些金币，每个人每次操作可以选择一级台阶将上面的一些金币放到下一级；不能操作的输。
结论：所有奇数级台阶上的金币数量异或起来就等于这个游戏的 SG 值。
简要证明：偶数级台阶可以是没有用的，因为一个人进行完一次偶数级操作后，另一个人可以再把那些金币放到更下面的一级，抵消这个操作；而操作奇数格相当于删除这些金币。这个思想很有意思。

$\left\lceil\frac{m+1}{2}\right\rceil$ $0$ $n$ $2k\times 2^i$ $\pmatrix{m\\2k}$ 。

C2. 砖块

题意：

$n,q(\le 2\times 10^5)$ $n$ $q$ 表示操作次数。
$x$ $x$ 元素都必须在序列中连续。
$x$ $y$ $cnt[x]$ $cnt[x]$ $x$ 元素的个数。
$q$ 次询问，每次询问单点修改一个位置的值，求修改完之后最小花费使得序列满足目标状态。
注意：更新不是独立的，之前的更新会保留。

题解：

$l$ $r$ $[l,r]$ 中的元素都得是相同的。这样的区间相等的限制是具有传递性的；在充分考虑其传递性后，会把原序列划分成若干段，其中每段中都得转化成一种相同的元素，每段的贡献相当于其长度减去区间众数。

$q=0$ $O(n)$ $O(n\log_2{n})$ 的。

$q\le 2\times 10^5$ 时，直接线段树分治。但是这么做复杂度显然是错误的，不能把均摊的东西外面再套上一个其他什么东西是吧。而导致其复杂度错误的根源在于每次都会删除再恢复很多区间——这启示我们直接用fhq-treap 之类的东西来维护，每次合并区间直接 splitmerge $O(n\log_2^2{n})$ 了。这个做法非常暴力，因此也能使用于较多情况，即处理有需要均摊结合线段树分治类的问题。

D2. 树哥

题面：

$n$ 个点的树，每个节点初始时是黑色或白色。
$u$ $1$ $u$ 路径上的所有点染成黑色，谁先无法操作谁输。
$n\le 10^5$ 。

题解：

$SG_u$ $u$ $SG$ 值，于是我写下了第一个假结论：

SG_u=\left(\bigoplus_{s\in son_u}SG_v\right)+1-vl_u

$SG$ $mex$ $SG$ $\boldsymbol{T}_u$ $u$ 子树所有后继状态构成的集合，那么我们可以得到如下的转移方程：

\boldsymbol{T}_u=\bigcup_{s\in son_u}{\left\{x\bigoplus_{t\in son_s,t\neq s}{SG_v} \mid x\in\boldsymbol{T}_v\right\}}

直接用带翻转标记的 01 Trie 合并维护即可；注意一定要带标记，不能在合并时再计算翻转，因为子树下面可能挂着一堆尚未被翻转的点。

solve(u,k) $u$ $k$ 的方案，直接递归下去执行即可。

A3. 数组

题意：

$n$ $a$ $n - 1$ $b$ $a$ 数组值收敛
$i$
$a_i = \min\left(a_i, \frac{a_i + a_{i + 1} - b_i}{2}\right),\ a_{i + 1} = \max\left(a_{i + 1}, \frac{a_i + a_{i + 1} + b_i}{2}\right)$ （没有取整）
$F(a, b)$ $a_1$ 的值
$b$ $n$ $c$ $\forall i \in [1, n],\ 0 \le a_i \le c_i$
$q$ $F(a, b) \ge x$ $a$ $1\ 000\ 000\ 007$ $n,a,c\le 100$ $q\le 10^5$ 。

题解：

超出了我的语言表达能力，因此咕咕咕。