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)。