A：

赛时发了什么疯非要来冲这题。

不妨计各种颜色的宝石为 0/1。

考虑记前缀和的最大值为 $S_{max}$，最小值为 $S_{min}$，于是总的限制为 $|S_{max}-S_{min}|\leq k$。

考虑反向维护这个限制，即枚举一个 $i$，然后钦定 $i\leq S_{min}\leq S_{max}\leq i+k$，计算对应的序列个数。然后考虑一个实际差值为 $\Delta=|S_{max}-S_{min}|$ 的序列，会被统计 $k-\Delta+1$ 次。记 $calc(k)$ 为上述过程计算出的序列个数，于是有最终答案为 $calc(k)-calc(k-1)$。

考虑 $calc(k)$ 如何计算。考虑把一个 $0$ 看做是在平面直角坐标系上让 $x$ 坐标 $+1$，一个 $1$ 为让 $y$ 坐标 $+1$，于是问题转化为，从 $(0,0)$ 出发，任意时刻在 $y=x+i$ 和 $y=x+i+k$ 之间，每次可以向右或向上走一步，问走到 $n$ 的方案数。

我们考虑条件为不能经过 $y=x+i-1$ 和 $y=x+i+k+1$。我们记一次经过第一条直线的事件为 $A$，第二条直线为 $B$，我们考虑对形如 $AABABBBA\cdots$ 的前缀做容斥。

我们把所有 $A$ 合并在一起，所有 $B$ 合并在一起，变成 $ABABA\cdots$，然后一次经过 $A$ 可以用经典卡特兰容斥理解为沿着 $y=x+i-1$ 翻折。

同理 $AB$ 即为先沿着 $y=x+i-1$ 翻折，再沿着 $y=x+i+k+1$ 翻折，我们减去翻折了奇数次的结果，加上翻折了偶数次的结果，即可得到最后答案。

B：

签到题目。

考虑到当前点最多从前一百个点转移（$d_i\leq100$），将式子放进矩阵里加速就行。

复杂度 $\mathcal O(d^3 \ log k)$。

C：

没有这题。

D：

开场觉得是个简单扫描线，写完 A 之后发现假了，不过绑包了居然没爆蛋（？

题解说这才是签子，没看出来。

不过正解还是扫描线。

考虑对每种活动区间 $[l,r]$ 增加两维 $l',r'$ 分别表示移除左边界挡板和右边界挡板之后的活动范围为 $(l',r)$ 与 $(l,r')$。那么两个区间 $(l_1,r_1,l_1',r_1')$,$(l_2,r_2,l_2',r_2')$ 能够同时坐人当且仅当 $l_1\ge r_2'$ 且 $l_2'\ge r_1$。

由于不同的区间最多只有 $4n$ 个，于是可以直接扫描线+set 维护找到。将所有区间按 $r'$ 排序，记录 $f_i/g_i$ 表示考虑了前 $i$ 个区间，此时最多能坐多少人，并且在坐最多人的基础上最小的 $r$，那么对于某个区间 $(l,r,l',r')$ 有转移：

$$(f_{r'},g_{r'})\gets(f_{l}+1,r)\ \text{if}\ (g_l\le l')\\ (f_i,g_i)\gets (f_{i-1},g_{i-1})$$

时间复杂度 $\mathcal O(n\log n)$。

---

然后就去体活了（喜，但是打球的时候很饿所以恼了。