P2801 教主的魔法

    • 2.1K通过
    • 7.5K提交
  • 题目提供者 BDF1
  • 评测方式 云端评测
  • 标签 模拟 高性能
  • 难度 提高+/省选-
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 体验新版界面

    最新讨论 显示

    推荐的相关题目 显示

    题目描述

    教主最近学会了一种神奇的魔法,能够使人长高。于是他准备演示给XMYZ信息组每个英雄看。于是N个英雄们又一次聚集在了一起,这次他们排成了一列,被编号为1、2、……、N。

    每个人的身高一开始都是不超过1000的正整数。教主的魔法每次可以把闭区间[L, R](1≤L≤R≤N)内的英雄的身高全部加上一个整数W。(虽然L=R时并不符合区间的书写规范,但我们可以认为是单独增加第L(R)个英雄的身高)

    CYZ、光哥和ZJQ等人不信教主的邪,于是他们有时候会问WD闭区间 [L, R] 内有多少英雄身高大于等于C,以验证教主的魔法是否真的有效。

    WD巨懒,于是他把这个回答的任务交给了你。

    输入输出格式

    输入格式:

    第1行为两个整数N、Q。Q为问题数与教主的施法数总和。

    第2行有N个正整数,第i个数代表第i个英雄的身高。

    第3到第Q+2行每行有一个操作:

    (1) 若第一个字母为“M”,则紧接着有三个数字L、R、W。表示对闭区间 [L, R] 内所有英雄的身高加上W。

    (2) 若第一个字母为“A”,则紧接着有三个数字L、R、C。询问闭区间 [L, R] 内有多少英雄的身高大于等于C。

    输出格式:

    对每个“A”询问输出一行,仅含一个整数,表示闭区间 [L, R] 内身高大于等于C的英雄数。

    输入输出样例

    输入样例#1: 复制
    5 3
    
    1 2 3 4 5
    
    A 1 5 4
    
    M 3 5 1
    
    A 1 5 4
    输出样例#1: 复制
    2
    3
    

    说明

    【输入输出样例说明】

    原先5个英雄身高为1、2、3、4、5,此时[1, 5]间有2个英雄的身高大于等于4。教主施法后变为1、2、4、5、6,此时[1, 5]间有3个英雄的身高大于等于4。

    【数据范围】

    对30%的数据,N≤1000,Q≤1000。

    对100%的数据,N≤1000000,Q≤3000,1≤W≤1000,1≤C≤1,000,000,000。

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。