#P3709. 大爷的字符串题

    ID: 5118 远端评测题 1000ms 125MiB 尝试: 1 已通过: 1 难度: 10 上传者: 标签>莫队离散化洛谷原创O2优化洛谷月赛

大爷的字符串题

题目背景

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

/*被和谐部分*/

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

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

题目描述

给你一个字符串 aa,每次询问一段区间的贡献。

贡献定义:

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

  • 如果 SS 为空,你 rp 减 11
  • 如果 SS 中有一个元素不小于 xx,则你 rp 减 11,清空 SS
  • 之后将 xx 插入 SS

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

询问之间不互相影响~

输入格式

第一行两个整数 nnmm,表示字符串长度与询问次数。

之后一行 nn 个数,第 ii 个整数表示给出的字符串的第 ii 个字符 xix_i

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

输出格式

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

3 3
3 3 3
3 3
3 3
3 3
-1
-1
-1

提示

数据规模与约定

  • 对于 10%10\% 的数据,是样例。
  • 对于另外 10%10\% 的数据,保证 n,m100n,m \le 100
  • 对于另外 10%10\% 的数据,保证 n,m103n,m \le 10^3
  • 对于另外 10%10\% 的数据,保证 n,m104n,m \le 10^4
  • 对于另外 10%10\% 的数据,保证 n,m105n,m \le 10^5
  • 对于 100%100\% 的数据,1n,m2×1051 \leq n,m \le 2 \times10^51ai1091 \leq a_i \leq 10^91l,rn1 \leq l, r \leq n

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

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