扩展单调栈&扫描线维护汗青信息

同样来自模拟赛 T4。
引入

思量如下题目：
给定一个初始为空的数列 \(a\)，有 \(c\) 次操纵，每次操纵形如：

• \(1\) \(x\)：将值 \(x\) 放入 \(a\) 的末端。（包管这个操纵有 \(n\) 次，\(n\) 在一开始给定）
  
• \(2\) \(x\)：查询当前序列全部长度为 \(x\) 的区间的代价和，答案对 \(998244353\) 取模。
  

此中一个长度为 \(x\) 的区间的代价界说为：在输入一开始会给定一个定值 \(m\)，若 \(xa_x\) 时，\(x\) 就不再是关键位置了，要把它从链表中删除，不难证实这种情况等价于 \(a_x\) 原先是 \([x,n]\) 的第 \(m\) 大。
以是不管是从判定一个位置是否仍然是关键位置的角度，照旧从维护区间代价的角度（由于维护区间代价的时间你须要删去最小值的贡献加入 \(w\) 的贡献），我们都应该去维护一个 \(mn_x\) 表现 \(S_{x,n}\) 的第 \(m\) 大的值。
那怎么维护呢，我们思量从前去后更新（从你竣事遍历的位置的后继开始到链表尾）。假设当前须要更新 \(x\) 的 \(mn_x\)，他的前驱为 \(x'\) 已经更新好了，设加入 \(w\) 前 \(mn_{x'}\) 为 \(old_{x'}\)，加入 \(w\) 后为 \(mn_{x'}\)：

• \(n+1-x+1\le m\)：直接令 \(\min(mn_x,w) \to mn_x\) 即可。
  
• 否则，由于我们在出现 \(\ge m\) 个 \(>w\) 的数时会直接退出，以是肯定有 \(w>old_{x'}\)，也就是说原先 \(old_{x'}\) 是 \([x',n]\) 的第 \(m\) 大，如今就是 \([x',n+1]\) 的第 \(m+1\) 大了：
  
  
  
  • 若 \(a_{x'}=old_{x'}\)，此时 \(a_{x'}\) 不再是 \([x',n+1]\) 的第 \(m\) 大，因此 \([x,n+1]\) 的第 \(m\) 大就是 \([x',n+1]\) 的第 \(m\) 大：\(mn_x=mn_{x'}\)
    
  • 否则，\([x,n+1]\) 的第 \(m\) 大是 \([x',n+1]\) 的第 \(m+1\) 大，即原先的 \(old_{x'}\)（由于还要去掉 \(a_{x'}\)）：\(mn_x=old_{x'}\)。
    
  
  

但是如许你会发现第一个位置是没法更新的，不外由于只有这么一个位置，以是我们直接暴力重构盘算出第 \(m\) 大即可。（这里的暴力只要复杂度跟你遍历过的位置个数线性就可以了，比如你可以用 STL 提供给你的 nth_element）。
末了 \(n+1\) 固然是一个关键位置，把他加入链表。
然后我们分析一下 ex 单调栈的复杂度：
<ul>对于遍历到的 \(>w\) 的数，我们只会遍历 \(\le m\) 个。
对于遍历到的 \(=mod)?(x+y-mod)x+y); }PII operator + (const PII &x,const PII &y){ return mk((x.fi+y.fi)%mod,(x.se+y.se)%mod); }struct DS{        int B,n,len,t,L[N],R[N],id[N