XSY4313 seq

显然有两个 $\log$ 的做法： $$\sum_{\begin{aligned}&i\le j\le r_i\\&r_j-j<d_i\end{aligned}}\text{S}(j,\min\{r_i,r_j\})=\sum_{\begin{aligned}&i\le j\\&r_j-j<d_i\\&r_j<r_i\end{aligned}}\text{S}(j,r_j)+\sum_{\begin{aligned}&i\le j\le r_i\\&r_j-j<d_i\\&r_j\ge r_i\end{aligned}}\text{S}(j,r_i)$$ 类似三维偏序

考虑一个阈值 $r_i-d_i$，分别考虑 $j$ 在区间 $[i,r_i-d_i]$ 和 $(r_i-d_i,r_i]$ 的情况

$$\begin{aligned} &\sum_{\begin{aligned}&i\le j\le r_i\\&r_j-j<d_i\end{aligned}}\text{S}(j,\min\{r_i,r_j\})\\ =&\sum_{\begin{aligned}&i\le j\le r_i-d_i\\&r_j-j<d_i\end{aligned}}\text{S}(j,r_j)+\sum_{\begin{aligned}&r_i-d_i< j\le r_i\\&r_j-j<d_i\end{aligned}}\text{S}(j,\min\{r_i,r_j\})\\ =&\sum_{\begin{aligned}&i\le j\le r_i-d_i\\&r_j-j<d_i\end{aligned}}\text{S}(j,r_j)+\sum_{r_i-d_i< j\le r_i}\text{S}(j,\min\{r_i,r_j\})-\sum_{\begin{aligned}&r_i-d_i< j\le r_i\\&r_j-j\ge d_i\end{aligned}}\text{S}(j,r_i)\\ =&\sum_{\begin{aligned}&i\le j\le r_i-d_i\\&r_j-j<d_i\end{aligned}}\text{S}(j,r_j)+\sum_{\begin{aligned}&r_i-d_i< j\le r_i\\&r_j\le r_i\end{aligned}}\text{S}(j,r_j)+\sum_{\begin{aligned}&r_i-d_i< j\le r_i\\&r_j>r_i\end{aligned}}\text{S}(j,r_i)-\sum_{\begin{aligned}&r_i-d_i< j\le r_i\\&r_j-j\ge d_i\end{aligned}}\text{S}(j,r_i) \end{aligned}$$

这四个东西都可以第一维差分，第二维树状数组做