2026 杭电暑期多校 8-1002-会自动求和的序列 · znzryb
# 题目大意
### 会自动求和的序列
<!-- Notion block type: heading_4 -->
有两个长度为 $n$ 的序列 $a$ 和 $b$。
接下来依次经过 $m$ 天。每天开始时,对于所有 $1\le i\le n$,先执行 $a_i\leftarrow a_i+b_i$,然后执行当天的一次操作。
操作共有以下两种:
- `1 l r x`:对于所有 $l\le i\le r$,执行 $b_i\leftarrow b_i+x$。
- `2 l r`:求当前的区间和 $\sum_{i=l}^{r}a_i$ 对 $2^{64}$ 取模后的结果。
<!-- Notion block type: heading_4 -->
第一行包含一个整数 $T$,表示测试用例的组数。
对于每组测试用例:
- 第一行包含两个整数 $n,m$,分别表示序列长度和天数;
- 接下来 $n$ 行,第 $i$ 行包含两个整数 $a_i,b_i$,表示两个序列的初始值;
- 接下来 $m$ 行,每行包含一次操作,格式为 `1 l r x` 或 `2 l r`。
对于 OJ 中唯一一组正式测试数据,保证:
- $T=10^4$;
- $2\le n\le 5\times 10^5$;
- $1\le m\le 5\times 10^5$;
- $1\le a_i,b_i\le 10^9$;
- $1\le l<r\le n$;
- $1\le x\le 10^9$;
- $\sum n=10^6$;
- $\sum m=10^6$。
<!-- Notion block type: heading_4 -->
对于每次第二类操作,输出一行一个整数,表示询问结果对 $2^{64}$ 取模后的值。
结果应表示为 $0$ 到 $2^{64}-1$ 之间的十进制整数。
<!-- Notion block type: heading_4 -->
**输入**
```
1
4 4
1 2
2 1
1 1
2 2
2 1 4
1 1 2 1
2 1 3
2 2 4
```
**输出**
```
12
18
23
```
<!-- Notion block type: heading_4 -->
初始时 $a=[1,2,1,2]$,$b=[2,1,1,2]$。
- **第** $1$ **天**:先令 $a_i\leftarrow a_i+b_i$,得到 $a=[3,3,2,4]$。操作为 `2 1 4`,输出 $3+3+2+4=12$。
- **第** $2$ **天**:先令 $a_i\leftarrow a_i+b_i$,得到 $a=[5,4,3,6]$。操作为 `1 1 2 1`,将 $b_1,b_2$ 各加 $1$,得到 $b=[3,2,1,2]$,无输出。
- **第** $3$ **天**:先令 $a_i\leftarrow a_i+b_i$,得到 $a=[8,6,4,8]$。操作为 `2 1 3`,输出 $8+6+4=18$。
- **第** $4$ **天**:先令 $a_i\leftarrow a_i+b_i$,得到 $a=[11,8,5,10]$。操作为 `2 2 4`,输出 $8+5+10=23$。
# 思路讲解

其实只需要维护2个线段树,一个维护这个 $x$ 的和,一个维护一下 $x \times p$ 的和就可以了。
```cpp
rep(i, 1, m)
{
int op, l, r;
cin >> op >> l >> r;
if (op == 1)
{
ull x;
cin >> x;
treeX.rangeAdd(l, r, x);
treeXP.rangeAdd(l, r, x * i);
}
else
{
ull base = (sa[r] - sa[l - 1]) + (sb[r] - sb[l - 1]) * i;
// 这个就是上面公式中的 x*t,这个就是上面公式中的 x*p
ull update = treeX.query(l, r) * i - treeXP.query(l, r);
cout << base + update << '\n';
}
}
```
# AC代码
::: 猫尾草的 AC 代码
```cpp
// teamname:猫尾草
#include <iostream>
#include <algorithm>
#include <iomanip>
#include <cstring>
#include <climits>
#include <cmath>
#include <vector>
#include <bitset>
#include <queue>
#include <set>
#include <map>
#define rep(i, a, n) for(int (i) = (a); (i) <= (n); (i) ++)
#define per(i, a, n) for(int (i) = (n); (i) >= (a); (i) --)
#define vi vector<int>
#define vvi vector<vector<int>>
#define vb vector<bool>
#define vll vector<ll>
#define vull vector<ull>
#define vvll vector<vector<ll>>
#define vpll vector<pair<ll, ll>>
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
using namespace std;
using ll = long long;
using ull = unsigned long long;
const char* sep[2] = {"", "\n"};
const ll N = 1e9 + 7, MOD = 998244353;
template<typename T>
struct SegmentTree
{
#define mid ((l + r) >> 1)
#define lp (p << 1)
#define rp (p << 1 | 1)
int n;
vector<T> d, add;
SegmentTree(int n_) : n(n_), d(4 * n), add(4 * n, 0) {}
SegmentTree(int n_, const vector<T>& a) : n(n_), d(4 * n), add(4 * n, 0)
{
build(1, 1, n, a);
}
void build(int p, int l, int r, const vector<T>& a)
{
if (l == r)
{
d[p] = a[l];
return;
}
build(lp, l, mid, a);
build(rp, mid + 1, r, a);
pull(p);
}
void pull(int p)
{
d[p] = d[lp] + d[rp];
}
void push(int p, int l, int r)
{
if (add[p] != 0 && l != r)
{
_add(lp, l, mid, add[p]);
_add(rp, mid + 1, r, add[p]);
add[p] = 0;
}
}
void _add(int p, int l, int r, T v)
{
d[p] += v * (r - l + 1);
add[p] += v;
}
void rangeAdd(int p, int l, int r, int ql, int qr, T v)
{
if (ql > r || l > qr) return;
if (ql <= l && r <= qr) return _add(p, l, r, v);
push(p, l, r);
rangeAdd(lp, l, mid, ql, qr, v);
rangeAdd(rp, mid + 1, r, ql, qr, v);
pull(p);
}
T query(int p, int l, int r, int ql, int qr)
{
if (ql > r || l > qr) return {};
if (ql <= l && r <= qr) return d[p];
push(p, l, r);
return query(lp, l, mid, ql, qr) + query(rp, mid + 1, r, ql, qr);
}
void rangeAdd(int l, int r, T v) { rangeAdd(1, 1, n, l, r, v); }
T query(int l, int r) { return query(1, 1, n, l, r); }
};
void solve()
{
int n, m;
cin >> n >> m;
vull a(n + 1), b(n + 1), sa(n + 1, 0), sb(n + 1, 0);
rep(i, 1, n)
{
cin >> a[i] >> b[i];
sa[i] = sa[i - 1] + a[i];
sb[i] = sb[i - 1] + b[i];
}
SegmentTree<ull> treeX(n), treeXP(n);
rep(i, 1, m)
{
int op, l, r;
cin >> op >> l >> r;
if (op == 1)
{
ull x;
cin >> x;
treeX.rangeAdd(l, r, x);
treeXP.rangeAdd(l, r, x * i);
}
else
{
ull base = (sa[r] - sa[l - 1]) + (sb[r] - sb[l - 1]) * i;
ull update = treeX.query(l, r) * i - treeXP.query(l, r);
cout << base + update << '\n';
}
}
return;
}
int main()
{
//freopen(".in", "r", stdin);
//freopen(".out", "w", stdout);
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T = 1;
cin >> T; cin.ignore();
while (T --)
solve();
return 0;
}
```
:::
::: 源代码
```cpp
```
:::
# 心路历程(WA,TLE,MLE……)