比赛场次 | 358 |
---|---|
比赛名称 | 数列操作练习题 |
比赛状态 | 已结束比赛成绩 |
开始时间 | 2017-03-18 19:00:00 |
结束时间 | 2017-03-19 23:59:59 |
开放分组 | 全部用户 |
注释介绍 | 数列操作按顺序做=ω= 祝愿大家颓得好成绩 |
题目名称 | 数列操作λ |
---|---|
输入输出 | meatv.in/out |
时间限制 | 3000 ms (3 s) |
内存限制 | 512 MiB |
测试点数 | 10 简单对比 |
用户 | 结果 | 时间 | 内存 | 得分 |
---|
给出一个长度为$N$的数组和$Q$次操作和一个数$K$
操作分两种
1.给出$p,x$将位置$p$加上一个值$x$
2.给出$n$询问到位置$n$的$K$次前缀和$\mod 998244353$
至于什么是K次前缀和,你可以这么理解:
对于一个数组$a$,对于所有$i$从$1$到$N-1$按顺序令$a_i=a_i+a_{i-1}$可以得到$1$次前缀和,再次执行该操作可以得到$2$次前缀和,即$K$次前缀和就是执行$K$次操作后的结果。例如对于$\{1,1,1,1,1\}$的$1$次前缀和就是$\{1,2,3,4,5\}$,$2$次前缀和就是$\{1,3,6,10,15\}$
$N\le10^5,Q\le 10^5,K\le 2^{30}$
$操作1不超过500次$
第一行三个整数$N,K,Q$
第二行$N$个数,第$i$个数为数组中位置为$i-1$的数
接下来$Q$行每行行首一个数$op$表示操作种类
若$op=1$则接下来有两个整数$p,x$
若$op=2$接下来一个整数$n$
对于每个$op=2$的操作,输出对应的值
5 1 2 1 1 1 1 1 1 1 1 2 3
5
对于第$p$个测试点有
$Q,N\le p^2*1000$
$K\le p^2*10737418$
51nod 1172 +强行嵌套