TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  训练指南  考试列表  判题结果  信息发布  解题排行
  • 首页
  • 题库
  • P2691
  • 题目
  • P2691【冬季集训】Mex II
    限制 : 时间限制 : 25000 MS   空间限制 : 123456 KB
    问题描述

    在SG定理中,对于一个由自然数组成的有限集合S,mex{S}定义为不在集合S中的最小自然数,例如mex{0,1,2}=3,mex{2,3,5}=0.
    给你一个长度为N的非负整数序列{A1,A2, ... ,AN},定义mex(l,r)=mex{Al,Al+1, ... ,Ar}.
    现有Q个询问,每次提问mex(l,r)的值.

    输入格式

    第一行两整数N,Q,
    第二行N个整数,第i个数为Ai
    接下来Q行每行两个数为一次提问。

    输出格式

    对每次提问输出一行,为这次提问的答案。

    样例输入

    7 5
    0 2 1 0 1 3 2
    1 3
    2 3
    1 4
    3 6
    2 7

    样例输出

    3
    0
    3
    2
    4

    提示

    1<=N<=200000
    1<=Q<=200000
    0<=Ai<=200000


    来源  BZOJ 3339