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)\)。
然后就去体活了（喜，但是打球的时候很饿所以恼了。
标签：总结,10,2024.10,min,max,翻折,leq,考虑,calc From： https://www.cnblogs.com/Mitishirube0717/p/18456261