2026 杭电暑期多校 8-1002-会自动求和的序列

题目大意

会自动求和的序列

有两个长度为 $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}$ 取模后的结果。

第一行包含一个整数 $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$。

对于每次第二类操作，输出一行一个整数，表示询问结果对 $2^{64}$ 取模后的值。

结果应表示为 $0$ 到 $2^{64}-1$ 之间的十进制整数。

输入

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

初始时 $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$ 的和就可以了。

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 代码

// 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;
}

源代码

心路历程（WA，TLE，MLE……）