P4215 踩气球

    • 18通过
    • 42提交
  • 题目提供者 chen_zhe 管理员
  • 评测方式 云端评测
  • 标签 高性能
  • 难度 省选/NOI-
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 最新讨论 显示

    推荐的相关题目 显示

    题目描述

    六一儿童节到了, SHUXK 被迫陪着M个熊孩子玩一个无聊的游戏:有N个盒子从左到右排成一排,第i个盒子里装着 $A_i$ 个气球。 SHUXK 要进行Q次操作,每次从某一个盒子里拿出一个没被踩爆的气球,然后熊孩子们就会立刻把它踩爆。 这M个熊孩子每个人都指定了一个盒子区间[ $L_i$ , $R_i$ ]。 如果某一个时刻,一个熊孩子发现自己选定的盒子区间[ $L_i$ , $R_i$ ]中的所有气球都已经被踩爆了,他就会非常高兴(显然之后他一直会很高兴)。 为了不辜负将自己的任务强行塞给 SHUXK 的那个人的期望, SHUXK 想向你询问: 他每次操作过后会有多少个熊孩子很高兴。

    输入输出格式

    输入格式:

    第一行包含两个正整数N和M,分别表示盒子和熊孩子的个数。 第二行包含N个正整数Ai( 1<= $A_i$ <= $10^5$ ),表示每个盒子里气球的数量。 以下M行每行包含两个正整数Li, Ri( 1<= $L_i$ <= $R_i$ <=N),分别表示每一个熊孩子指定的区间。 以下一行包含一个正整数Q,表示 SHUXK 操作的次数。 以下Q行每行包含一个正整数X,表示这次操作是从第X个盒子里拿气球。为了体现在线,我们对输入的X进行了加密。 假设输入的正整数是 $\hat{x}$ ,那么真正的X=( $\hat{x}$ +Lastans−1)Mod N +1。其中Lastans为上一次询问的答案。对于第一个询问, Lastans=0。 输入数据保证1<= $\hat{x}$ <= $10^9$ , 且第X个盒子中有尚未被踩爆的气球。 N<= $10^5$ ,M<= $10^5 $ ,Q<= $10^5$

    输出格式:

    包含Q行,每行输出一个整数,表示 SHUXK 一次操作后询问的答案。答案的顺序应与输入数据的顺序保持一致。

    输入输出样例

    输入样例#1: 复制
    5 3
    1 1 1 1 1
    5 5
    2 2
    1 3
    5 
    4 
    2 
    5 
    2 
    3
    输出样例#1: 复制
    0 
    1 
    1 
    2 
    3
    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。