P5358 [SDOI2019]快速查询

    • 146通过
    • 304提交
  • 题目提供者 一扶苏一
  • 评测方式 云端评测
  • 标签 各省省选 2019 山东 O2优化
  • 难度 省选/NOI-
  • 时空限制 2000ms / 512MB

题解

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

    最新讨论 显示

    推荐的相关题目 显示

    题目描述

    给定一个长度为 $n$ 的整数数列,里面的元素依次编号为 $a_1,~a_2,~a_3,~\dots,~a_n$。初始的时候,所有元素都为零。现在按照时间顺序提供了若干次关于这个数列的修改或询问,每一次修改或询问一定为以下六种情况之一:

    • 1 i val :将 $a_i$ 赋值为给定整数 $val$;

    • 2 val :将所有元素同时加上 $val$;

    • 3 val :将所有元素同时乘上 $val$;

    • 4 val :将所有元素同时赋值为 $val$;

    • 5 i :询问第 $i$ 个元素 $ai​ 现在的值是多少;

    • 6 :询问现在所有元素的和。

    输入输出格式

    输入格式:

    为了避免读入太大,输入文件采取如下的形式。

    第一行给定整数 $n$,表示给定数列长度为 $n$。 第二行给定整数 $q$,并且之后的 $q$ 行,每一行提供一个修改或询问,输入的格式与题目所述一致,请参见样例。 我们称上述给定的修改或询问为标准操作。 之后给定一个整数 $t$,并且之后的 $t$ 行每行给定两个正整数 $a_i$ 和 $b_i$,这里的下标 $i$ 依次记为 $1$ 到 $t$ 。

    你需要对初始值全为零的长度为 $n$ 的序列做总计 $t\times q$ 次操作。 其中第 $\Big((i-1)q+j\Big)$ 次操作形如第 $\Big((a_i + j b_i) \mod{q} + 1\Big)$ 个给定的标准操作($1\le i\le t$ 且 $1\le j\le q$)。

    输出格式:

    输出一个整数,表示所有询问答案的累计和。

    因为答案可能很大,只要求输出其结果关于 $p=10^7+19$ 取模后的值。

    注意:若最终的累计和 ans 小于零,你应该输出 $\big((ans \mod{p})+p\big)\mod{p}$。

    输入输出样例

    输入样例#1: 复制
    7
    28
    6
    4 -192321079
    3 418379342
    1 3 189801569
    3 -840249197
    4 -751917965
    3 649799919
    1 5 -92666141
    6
    4 451258008
    5 1
    4 696880327
    3 772574465
    6
    4 301010289
    3 480168068
    5 3
    5 2
    4 840536237
    5 5
    5 4
    1 7 -792284106
    2 604521872
    3 966540578
    2 -381646699
    3 -939378260
    2 -20129935
    6
    2
    0 1
    197 199
    输出样例#1: 复制
    2816930

    说明

    子任务$1$:($50$分)$1\le n\le 500000$,$1\le q\le 10^5$ 且 $1\le t\le 5$,所有在输入中出现的$val$ 满足$-10^9\le val\le 10^9$,所有$a_i$和$b_i$满足$0\le a_i,b_i\le 10^9$

    子任务$2$:($50$分)$1\le n\le 10^9$,$1\le q\le 10^5$ 且 $1\le~t~\le~100$,所有在输入中出现的$val$ 满足$-10^9\le val\le 10^9$,所有$a_i$和$b_i$满足$0\le a_i,b_i\le 10^9$

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