Happy Sugar Life，but 2.73 kb

\(\text{poly log}\) 的感觉太难写了，那么考虑分块，先记询问的序列限制为 \([l,r]\)，值域限制为 \([x,y]\)，一个支配对为两个部分。

1. 散块内部。
2. 散块对散块。
3. 整块内部。
4. 整块对整块。
5. 散块对整块。

同样是 \(5\) 种贡献。

可以发现贡献 \(2,5\) 的序列不交，且两个部分一定有一个的长度 \(\le \sqrt n\)，那么可以枚举它的元素，然后查询另一部分值域在 \([x,y]\) 的点的数量，那么可以对序列差分，并维护一个 \(\text{O}(1)\) 查询的值域分块。

考虑贡献 \(3\)，序列固定，但是不好确定值域的限制 \([l,r]\)，那么可以用二维数组来限制它，考虑记 \(f_{l,r}\) 表示值域在 \([l,r]\) 的贡献，那么可以先离散化一下，然后做容斥区间 \(\text{dp}\)，\(f_{l,r}=f_{l+1,r}+f_{l,r-1}-f_{l+1,r-1}+(pos_l<pos_r)\)。

再考虑贡献 \(1\)，看见题解区有常数极大且不是很好写的类 \(\text{dp}\) 做法和复杂度不太正确的分治做法，只能说太抽象了。这边提供一个简单的做法，肯定是先要枚举每个块的，那么同样考虑在序列上差分，如果说我们像贡献 \(2,5\) 那样差分，会少减去一部分在 \(l-1\) 前另一部分在 \([l,r]\) 的，考虑换一个方式，如果扫到一个 \(l\)，我们先用值域分块内已经有的，再枚举这个询问的区间，减去它们之间的贡献，如果扫到一个块内的元素，便加上值域分块中有的元素对它的贡献。

最后考虑贡献 \(4\)，感觉不太可以序列分块，但是又觉得只能差分，那么换一个维度，在值域上差分，贡献为 \(([1,y]_{\text{ans}}-[1,x-1]_{\text{ans}})-[1,x-1]_{\text{num}} \times [x,y]_{\text{num}}\)，感觉两个部分只能分开维护，考虑前半部分，在值域上从小到大扫，但是不能直接枚举每次询问包含的块包含的元素来计算贡献，还是可以直接用二维数组限制，那么可以记 \(g_{l,r}\) 表示块 \([l,r-1]\) 对块 \(r\) 的贡献，那就可以直接做了；考虑后半部分，可以发现这两个矩形不交，自然想到扫每个块，同样需要此次查询块内的值域在 \([p,q]\) 的点，也需要离散化，可以和贡献 \(3\) 一起做，再对每个询问记录 \(cnt_i\) 表示它包含的块的前缀的 \([1,x-1]_{\text{num}}\) 的和即可。

\(\text{code}\)。