Glo
题面
考场
一看是一个最长上升子序列，只是带一点特殊的东西，再一看数据范围，根据已学知识要用单调栈搞一个 $\log$ 算法差不多能过。
然后开始看那个特殊的区间加操作。然后发现如果把一个区间加向后面拓展成后缀加，答案一定是不劣的，同理区间减扩展成前缀减。进一步我们发现最长上升子序列关心的只是他们之间的差值，所以数值本身意义不大，因此前缀减可以等效成后缀加，那么现在的问题就变成了要给一个后缀加上一个数之后的最长上升子序列了。
然后我考虑单调栈的做法，就是维护一个当前的上升子序列长度为 $x$ 的一个最小值，然后找到刚好比自己大的位置插进去，并更新答案。所以我的想法就是与此同时也在一个后缀的栈里面找到 $x-k$ 的位置，用那里的后缀最长下降子序列更新总的答案。但是这个栈是没办法回退的，所以我发现不能预处理一遍后缀栈然后在做前缀的时候退出上一位的影响。那就只能暴力做这里的栈了，这个做法要么时间爆炸要么空间爆炸。而我也没有什么进一步思路了。
看看部分分。
$k=0$
这个就是普通的最长上升子序列。直接做。
$k=1e9( \infin)$
这个已经不需要考虑 $x-k$ 在哪了，所有的后缀都能满足了。那直接正反求一遍，然后在中间用前后缀更新答案。
出分：$10pt.$ ？？？它 $subtask???$ 稍微改了改救回 $33.$
正解
上面的做法已经离得很近了。在处理前缀的时候，我们可以直接把那个值的答案记下来。就是那个前缀 $x$ 处的最长上升子序列，那么前缀上就必须大于 $x + k$。然后我们再倒着看，只要在每个地方加了之后在之前里面的答案中更新即可。具体而言就是：
记录一个 $f_i$ 表示在 $1 \to a_i$ 前缀上严格以 $a_i+k$ 结尾的最长上升子序列。那么在倒着做的时候，只需要在栈里面找 $a_i$ 的答案 $f_i$。
这个可以用单调栈实现，但是这次学会了另一种求最长上升子序列的方法：在值域上维护区间最大值。因为每一次要的是结尾比 $a_i$ 小的最长上升子序列，所以相当于求一个值域前缀 $\max.$ 这个离散化之后用线段树或者树状数组维护即可。也是一个 $\log$ 的。
$code:$ https://paste.ubuntu.com/p/2dnt4nTXrg/
Mobitel
题面
考场
没想到用 $dp.$ 写的爆搜加小剪枝，因为发现当大于的时候后面的方案数可以用组合数算了，就直接剪掉了。
出分：$10pt.$
正解
$dp.$ 因为大于 $n$ 没什么限制条件不好做，所以我们转化一下，转化成用整个的（也是一个组合数）减去小于 $n$ 的方案数，因此这个就可以 $dp$ 了。
设 $f_{i,j,m}$ 表示现在走到 $(i,j)$ 乘积是 $m$ 的方案数。然后转移转移到 $(i+1,j)$ 和 $(i,~j+1)$ 即可。这个复杂度是 $O(rsn)$ 的，肯定爆炸了。
所以考虑进一步转化，优化一下状态。因为发现最后能用到的空间其实是 $\large\frac{rest}{a_{i,j}}$ ，而 $\large\frac n x$ 的个数又只有 $2\sqrt n$ 个 ，所以可以把状态优化成 $f_{i,j,m}$ 表示走到 $(i,j)$ 还剩下 $m$ 给我们除。还是上面的转移，就可以继续做了。时间复杂度对了，但是发现空间炸了啊？能滚动吗？可以哦。每一次的值只和上一层有关，只要记这两层的就好了。
另外还有一个细节就是他要求的是大于等于 $n$ 的路径积方案数，所以求因子的时候注意要先 $n–.$
模数是 $1e9+7$ 不是 $998244353$！！！
$code:$ https://paste.ubuntu.com/p/qCc4dyDV4s/
Lottery
题面
考场
只想到了 $n^3$ 转移的暴力。其实是只去肝第一题了。。
出分：$25pt.$
正解
首先 $n^2$ 就有一个很巧妙简单的转移：可以通过去掉左边端点上的两个加上右边端点上的两个点，来实现同一长度的区间从左向右的移动 $O(1)$ 得到答案。然后发现 $n=1e4?$ $O(n^2)$ 预处理好像能过。
但是发现空间开的很小，所以需要优化一下空间。如果直接开 $1e4\times 1e4$ 的数组要几个 $GB$ 内存啊。然后询问很少啊？
那就说明没有询问到的长度是无效的。所以可以先把询问离线下来，去个重编个号每次只要记每个数询问处的答案即可。
具体实现类似一个离散化吧。
$code:$ https://paste.ubuntu.com/p/VtcCv5R4dp/