题解：P13979 数列分块入门 4

inperfectTower · 2025-09-08 11:12:18 · 题解

记 O(x) - O(y) 为单次修改复杂度 O(x)，单次查询复杂度 O(y)。

简要题意

有一个数列，你需要支持区间加上某一个数和查询区间和。n \le 3 \times 10^5。

解法

~我会线段树！~

考虑 区间修改，单点查询 中引入的分块思想，我们以 \sqrt{n} 为块长把整个序列分成一块一块。

由于我们要查询区间和，所以需要维护一个块内和。与 区间修改，单点查询 中一样，我们需要维护一个懒标记用于区间修改。在区间修改的时候块内的和直接加上 c \times len，其中 len 是块长。

区间查询的时候，散块暴力处理，整块直接查询块内和即可。

这是 O(\sqrt{n}) - O(\sqrt{n}) 的。

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int kB = 450; // 调试的时候可以把 kB 调小，但是记得提交时要改回去

int n, arr[300030], op, l, r, c, bt[300030], bel[300030], bs[300030], blen[300030];

signed main() {
  cin >> n;
  for(int i = 1; i <= n; i++) {
    cin >> arr[i];
    bel[i] = (i + kB - 1) / kB;
    bs[bel[i]] += arr[i], blen[bel[i]]++;
  }
  for(int i = 1; i <= n; i++) {
    cin >> op >> l >> r >> c;
    if(op == 0) {
      if(bel[l] == bel[r]) {
        for(int j = l; j <= r; j++) arr[j] += c, bs[bel[j]] += c;
      }else {
        if(bel[l] == bel[l - 1]) for(; bel[l] == bel[l - 1]; l++) arr[l] += c, bs[bel[l]] += c;
        if(bel[r] == bel[r + 1]) for(; bel[r] == bel[r + 1]; r--) arr[r] += c, bs[bel[r]] += c;
        for(int j = bel[l]; j <= bel[r]; j++) bt[j] += c, bs[j] += blen[j] * c; // 注意可能出现长度 < kB 的块
      }
    }else {
      int ans = 0;
      if(bel[l] == bel[r]) {
        for(int j = l; j <= r; j++) ans += arr[j] + bt[bel[j]];
      }else {
        if(bel[l] == bel[l - 1]) for(; bel[l] == bel[l - 1]; l++) ans += arr[l] + bt[bel[l]];
        if(bel[r] == bel[r + 1]) for(; bel[r] == bel[r + 1]; r--) ans += arr[r] + bt[bel[r]];
        for(int j = bel[l]; j <= bel[r]; j++) ans += bs[j];
      }
      cout << (ans % (c + 1) + (c + 1)) % (c + 1) << '\n';
    }
  }
  return 0;
}