这是一道模板题。给定一个长为 n 的数组 a ,下标从 1 开始。你需要维护 m 次下面两种操作:
1 x v
将下标为 x 的元素增加 v 2 x y
查询下标区间 [x,y] 的和为了避免输入过长,请使用下面的伪随机数生成器 C++ 代码生成数组 a 和操作。
如果您使用其他编程语言,请你自行实现下面的伪随机数生成器 >_<
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n, a[10000010], seed, m;
signed main()
{
scanf("%lld%lld%lld", &n, &m, &seed);
mt19937 mt(seed);
uniform_int_distribution<int> dist(0, 1e9);
uniform_int_distribution<int> dist_cmd(1, 2);
uniform_int_distribution<int> dist_x(1, n);
for (ll i = 1; i <= n; ++i)
{
a[i] = dist(mt);
}
while (m--)
{
ll cmd = dist_cmd(mt);
if (cmd == 1)
{
ll x = dist_x(mt), v = dist(mt);
//下面是你解本题的代码
}
else
{
ll x = dist_x(mt), y = dist_x(mt);
if (x > y)
{
swap(x, y);
}
//下面是你解本题的代码
}
}
return 0;
}
根据上述代码,不难看出 1\le x\le y\le n,1\le v,a_i\le10^9
输入
输入一行三个整数 n,m,seed(1\le n\le10^7,0\le m\le10^6,1\le seed\le10^9)
输出
对于每个操作二,输出一行一个整数代表答案。
样例
标准输入 复制文本 |
10 7 114514 |
标准输出 复制文本 |
4932912511 5610523959 3960056545 6486668779 |
提示
样例生成的数据为:
738472244 887271006 726035162 930666685 458070558 243583394 840774597 846511109 38832567 233880135
2 2 8
1 3 677611448
2 2 8
1 7 53793770
1 7 783518483
2 1 4
2 2 9