P3863 8月月赛C

    • 30通过
    • 514提交
  • 题目提供者Drench 站长团
  • 标签 洛谷原创 O2优化 高性能
  • 难度 省选/NOI-
  • 时空限制 2s / 512MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 推荐的相关题目

    题目描述

    给定一个长度为 $n$ 的序列,给出 $q$ 个操作,形如:

    $1~l~r~x$ 表示将序列下标介于 $[l,r]$ 的元素加上 $x$ (请注意,$x$ 可能为负)

    $2~p~y$ 表示查询 $a_p$ 在过去的多少秒时间内不小于 $y$ (不包括这一秒,细节请参照样例)

    开始时为第 $0$ 秒,第 $i$ 个操作发生在第 $i$ 秒。

    输入输出格式

    输入格式:

    第一行两个整数 $n,q$,意义如描述所述。

    接下来一行 $n$ 个整数 $a_i$,表示序列的每个元素的初始值。

    接下来 $q$ 行,每行第一个数为 $\text{opt}$,表示这次操作的类型。如果 $\text{opt} = 1$,后面紧跟三个整数 $l, r, x$,意义如描述所述;如果 $\text{opt} = 2$,后面紧跟两个整数 $p, y$,意义如描述所述。

    输出格式:

    对于每个操作 $2$,在一行内输出一个数表示答案。

    输入输出样例

    输入样例#1: 复制
    3 3
    1 3 5
    2 1 2
    1 1 2 -3
    2 1 1
    输出样例#1: 复制
    0
    2

    说明

    样例一说明:位置 $1$ 在第 $0$ 秒到第 $3$ 秒的值为 $1,1,-2,-2$。对于第一个查询,前 $1-1=0$ 秒中有 $0$ 秒时间不小于 $2$;对于第二个查询,前 $3-1=2$ 秒中有 $2$ 秒时间不小于 $1$,分别为第 $0$ 秒,第 $1$ 秒。

    对于 $30\%$ 的数据,保证 $n,q \leq 1000$

    对于 $70\%$ 的数据,保证 $n,q \leq 50000$

    对于 $100\%$ 的数据,保证 $2 \leq n,q \leq 100000$, $1 \leq l \leq r \leq n$, $1 \leq p \leq n$,$-10^9 \leq x,y,a_i \leq 10^9$

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