B. 下雨天

给定序列 $A_i$, 初始 $A_i=0$, 多次操作: 给定 $x$, $A_i\gets \min(\max(A_i+x,0),i)$, 每次求 $\sum A_i$. $n\le 10^9,q\le 10^6$.

注意到 $A_i$ 的图像为一条折线, 且每一段的斜率为 $0$ 或 $1$, 考虑维护折线. 对于每次操作, 若 $x>0$, 则会把 $A_i$ 的一段前缀换成 $A_i=i$; 若 $x<0$, 则会把一段前缀换成 $A_i=0$. 使用全局懒标记, 每次操作暴力寻找分界点并修改, 并维护折线下面积即可. 注意到每次操作至多增加一段, 故时间复杂度为 $O(q)$.

C. 游戏

$n$ 个点, 可黑白染色, 有 $m$ 段已被染成黑色, 你可以再染黑 $k$ 个长度为 $l$ 的段, 求最长的连续黑球数目. $m\le 10^5,n\le 10^9$.

设 $prv_i$ 表示从初始段 $i$ 的左端点 $-1$ 开始, 不断用长为 $l$ 的段往左覆盖, 首个被覆盖到且未被完全覆盖的初始段编号.

$f(i,j)=(i',c)$ 表示

C. 序列异或

给定 $n$, 求满足以下条件的严格递增序列 $[a_1,a_2,\ldots,a_m]$ ($m$ 自定, $a_i\in[1,2^n-1]$) 的个数: $\forall i:a_i\oplus a_{i+1}\oplus a_{i+2}\neq 0$. $n\le 2\times 10^7$.

发现若 $a_{i}\sim a_{i+2}$ 不满足条件, 设 $\text{hi}(x)$ 表示 $x$ 的最高位,