F.A.Qs Home Discuss ProblemSet Status Ranklist Contest 入门OJ LoginRegister 捐赠本站
Notice:本站提供各级各类比赛模拟题,有意者请联系本站邮箱Lydsy2012@163.com,欢迎各校教练、老师、家长来信咨询,非诚勿扰。
Problem 4865. -- [Ynoi2017]由乃运椰子

4865: [Ynoi2017]由乃运椰子

Time Limit: 4 Sec  Memory Limit: 10 MB
Submit: 218  Solved: 40
[Submit][Status][Discuss]

Description

二次元的由乃为了致富,决定引进日本的椰子树。由乃的椰子园十分现代化,椰子园中有一套独特的交通系统。但
是日本没有椰子树啊。。。所以这一切都是由乃的梦。由乃梦到自己的椰子树上涨了好多好多椰子,非常高兴--直
到她看到了一个数据结构题:给你一个字符串a,每次询问一段区间的贡献
贡献定义:
每次从这个区间中随机拿出一个字符x,然后把x从这个区间中删除,你要维护一个集合S如果S为空,你rp减1如果S
中有一个元素不小于x,则你rp减1,清空S之后将x插入S
由于由乃不是大爷,平时做过的题考试都不会考到,所以每次询问你搞完这段区间的字符之后最多还有多少rp?rp
初始为0询问之间不互相影响~由于由乃最近没事干,所以她决定卡常卡空间,请注意

Input

第一行两个数n,m,表示字符串长度与询问次数
之后一行n个数,表示字符串
由于你是大爷,所以字符集1e9
之后m行每行两个数,表示询问的左右区间

Output

m行,每行一个数表示答案

Sample Input

3 3
3 3 3
3 3
3 3
3 3

Sample Output

-1
-1
-1

HINT

1 <= n,m <= 60000,本题强制在线,每次操作的l和r要异或上上次答案本题强制在线,每次操作的l和r要异或上上次答案



Source

By 佚名提供

[Submit][Status][Discuss]

HOME Back