P14203 这次要永远 做朋友

考虑 $f(l+1,r) = t$ 的判断，设 $s_i = 2pre_i - i$，其中 $pre_i$ 为 $i$ 前缀 $t$ 的出现次数，那么就是 $s_r > s_l$。

观察 $s_i$ 有什么性质，若下一个数是 $t$ 就加 $1$，否则减 $1$，可以发现当 $t$ 出现次数较少时 $s$ 是几乎单降的，于是可以猜测有用的点（存在 $j>i \land s_j > s_i \lor j < i \land s_j < s_i$）只有 $O(cnt)$ 个，因为每次上升时只会影响多影响 $O(1)$ 个点。进一步地，所有答案的区间并大小也只有 $O(cnt)$，因为每次插入一个点最多拓展 $O(1)$ 位，所以也是对的。

枚举 $f(l,r)$，处理出这些有用的点（小于后缀最大值或大于前缀最小值），然后对每个区间先 $O(n)$ 求出 mex 大于等于 $t$ 的区间。令 $R_i$ 为以 $i$ 为左端点的最小右端点使得 mex $\ge t$，显然 $R_i$ 是单调不降的，从左到右扫，每次若删掉的数 $\le t$，则将 $R_{i+1} = \max(R_i,nxt_i)$，否则就是 $R_i$。

然后考虑求答案，也就是求逆序对个数，由于相邻 $s_i$ 的差不超过 $1$，所以在加入或删除点的时候有变化的个数也是 $O(1)$，直接双指针扫即可。

复杂度 $O(n)$。