「JOI 2020 Final」火事
题目大意：
给定一个长度为 \(N\) 的序列 \(S\) ，有 \(Q\) 个询问。初始为时刻 \(0\) ，且在 \(T\) 时刻时序列变换为 \(S'_i=\max_{i-T\le j\le i}\{S_j\}\) 。要求对询问给出的 \((T,L,R)\) ，回答 数据范围：\(1\le N,Q\le 2\times10^5,1\le S_i\le 10^9,1\le T,L,R\le N\) 。
题目难度：NOI/NOI+
标签：数据结构
解析：
子任务 \(1\) ，\(Q,N\le 200\) 。直接模拟即可，时间复杂度 \(O(QN^2)\) 。
子任务 \(2\) ，所有询问时间 \(T\) 相等。可以用单调队列一次性求出此时的 \(S\) 序列，前缀和处理后回答询问即可，时间复杂度 \(O(N)\) 。
子任务 \(3\) ，所有询问 \(L=R\) 。等价于单点查询，这可以通过 RMQ 做到 \(O(N\log N+Q)\) （ST表）或 \(O(N+Q\log N)\) （线段树）。
子任务 \(4\) ，\(S_i\le 2\) 。 首先发现每个 \(S_i\) 从某个时间开始就一直为 \(2\) ，所以每个点最多被影响一次。对询问按时间顺序排序，我们最多的单点修改次数不超过 \(N\) 。单点更新+区间求和，使用线段树或树状数组可以做到 \(O((N+Q)\log N)\) 。
最后考虑结合上述思想，推广至满分做法。
仍然可以按时间顺序处理所有询问，我们列出一个表格，第 \(i\) 行第 \(j\) 列的数表示时刻 \(i\) 时 \(S_j\) 的取值，可以发现每个数在表格里填充的部分呈平行四边形或直角梯形状。并且若找出 \(S_i\) 往左和右第一个大于它的数所在位置 \(l_i,r_i\) ，就可以求出平行四边形的四顶点坐标。
（之后就不会了，暂咕 QAQ