1727. 快速树状数组

这是一道模板题。给定一个长为 n 的数组 a ,下标从 1 开始。你需要维护 m 次下面两种操作:

  1. 1 x v 将下标为 x 的元素增加 v
  2. 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

登录以提交代码。
单点时限 1 秒
内存限制 128 MB
提交 30
通过 18