题面：大爷的字符串题

大秦为你打开题目传送门

题目背景

在那遥远的西南有一所学校，

/*被和谐部分*/

然后去参加该省省选虐场，

然后某蒟蒻不会做，所以也出了一个字符串题：

题目描述

给你一个字符串 $a$，每次询问一段区间的贡献。

贡献定义：

每次从这个区间中拿出一个字符 $x$ ，然后把 $x$ 从这个区间中删除，直到区间为空。你要维护一个集合 $S$。

  • 如果 $S$ 为空，你 rp 减 $1$。
  • 如果 $S$ 中有一个元素不小于 $x$，则你 rp 减 $1$，清空 $S$。
  • 之后将 $x$ 插入 $S$。

由于你是大爷，平时做过的题考试都会考到，所以每次询问你搞完这段区间的字符之后最多还有多少 rp？rp 初始为 $0$。

询问之间不互相影响~

输入格式

第一行两个整数 $n$，$m$，表示字符串长度与询问次数。

之后一行 $n$ 个数，第 $i$ 个整数表示给出的字符串的第 $i$ 个字符 $x_i$。

接下来 $m$ 行，每行两个整数 $l, r$，表示一次询问的区间。

输出格式

对于每次询问，输出一行一个整数表示答案。

样例 #1

样例输入 #1

1
2
3
4
5
3 3
3 3 3
3 3
3 3
3 3

样例输出 #1

1
2
3
-1
-1
-1

提示

数据规模与约定

  • 对于 $10\%$ 的数据，是样例。
  • 对于另外 $10\%$ 的数据，保证 $n,m \le 100$；
  • 对于另外 $10\%$ 的数据，保证 $n,m \le 10^3$；
  • 对于另外 $10\%$ 的数据，保证 $n,m \le 10^4$；
  • 对于另外 $10\%$ 的数据，保证 $n,m \le 10^5$；
  • 对于 $100\%$ 的数据，$1 \leq n,m \le 2 \times10^5$，$1 \leq a_i \leq 10^9$，$1 \leq l, r \leq n$。

保证数据像某省省选 day1T2 一样 sb，大家尽情用暴力水过题吧！

没事，你只要在一个好学校，就算这题只能拿到 10 分，也可以进队了。

思路

显而易见的，这道题作为臭名昭著的纯史题题面就是纯纯的勾十，我们来思考一下如何转化题意。

不难发现，把一个序列按照从小到大的顺序依次排列，就可以得到最优的结果，比如说下面这个序列和其排列后的结果。

这样排列一定是最小的结果，那么这样的序列能排多少个，一定是取决于区间众数的出现次数。就比如说上面的这个例子，区间众数是 $3$ 或 $4$ ，他们两个的出现次数都是 $2$ 所以答案就是配划分为了两个段，答案也就是 $-2\ \tt rp$ 。

那么问题也就成功转化为区间众数的出现次数。

那么这道题与蒲公英不一样的地方就是离线且只需要统计数量，那么我们就考虑如何统计。如果增加了一个数，自然可以更新答案，但是减少了一个数的时候，会不会影响答案？显然会，当众数的出现次数为 $x$ 但是你把所有出现次数为 $x$ 的数都删了一遍，那么只能把答案乖乖降到 $x-1$ 。那么已经有了这样的思考，答案已经呼之欲出

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
inline void Upd(int x, int f) {
    x = a[x];
    if(f == 1) {
        num[cnt[x]]--;
        cnt[x]++;
        num[cnt[x]]++;
        if(cnt[x] > ans) ans = cnt[x];
    }
    else {
        num[cnt[x]]--;
        if(num[cnt[x]] == 0 && ans == cnt[x]) ans--;
        cnt[x]--;
        num[cnt[x]]++;
    }
}

其他部分依然是纯模板。