RSQ and RAQ, mo's algorithm with update

http://ei1333.hateblo.jp/entry/2017/09/11/211011

触発された。n^1/3個に分割しておけば、(l,r)の組がO(n^2/3)通り、時間方向への移動でO(n)、なるほど計算量が落ちている。

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_2_G

このような単純な例であれば区間更新でもいける 0.17sec。imosっぽい操作であれば区間更新でも対応できる気がする。区間更新で、代替手法が存在しない例は存在するだろうか?

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

// cluster the elements by n^2/3.

int main() {
  int n, q;
  cin >> n >> q;

  vector<int> L(q), R(q), type(q), x(q);
  for (int i = 0; i < q; i++) {
    scanf("%d %d %d", &type[i], &L[i], &R[i]);
    if (type[i] == 0) {
      scanf("%d", &x[i]);
    }
  }

  vector<int> perm(q);
  for (int i = 0; i < q; i++) {
    perm[i] = i;
  }

  constexpr int S = 2000;
  sort(perm.begin(), perm.end(), [&](int i, int j) -> bool {
    if (L[i] / S != L[j] / S) return L[i] < L[j];
    if (R[i] / S != R[j] / S) return R[i] < R[j];
    return i < j;
  });

  vector<long long> dl(n + 2);
  vector<long long> dr(n + 2);

  int l = 0;
  int r = -1;
  int t = -1;
  long long s = 0;
  long long sl = 0;
  long long sr = 0;

  auto overlap = [&](int a, int b, int c, int d) {
    return max(0, min(b, d) - max(a, c) + 1);
  };

  auto extend_l = [&](int k) {
    sl += dl[k];
    s += sl;
  };

  auto extend_r = [&](int k) {
    sr += dr[k];
    s += sr;
  };

  auto shrink_l = [&](int k) {
    s -= sl;
    sl -= dl[k];
  };

  auto shrink_r = [&](int k) {
    s -= sr;
    sr -= dr[k];
  };

  auto extend_t = [&](int k) {
    if (type[k] == 1) return;
    dl[R[k]] += x[k];
    dl[L[k] - 1] -= x[k];
    dr[L[k]] += x[k];
    dr[R[k] + 1] -= x[k];
    if (L[k] <= l && l <= R[k]) sl += x[k];
    if (L[k] <= r && r <= R[k]) sr += x[k];
    s += overlap(l, r, L[k], R[k]) * x[k];
  };

  auto shrink_t = [&](int k) {
    if (type[k] == 1) return;
    dl[R[k]] -= x[k];
    dl[L[k] - 1] += x[k];
    dr[L[k]] -= x[k];
    dr[R[k] + 1] += x[k];
    if (L[k] <= l && l <= R[k]) sl -= x[k];
    if (L[k] <= r && r <= R[k]) sr -= x[k];
    s -= overlap(l, r, L[k], R[k]) * x[k];
  };

  vector<long long> ans(q);
  for (int i : perm) {
    if (type[i] == 0) continue;
    while (l > L[i]) extend_l(--l);
    while (r < R[i]) extend_r(++r);
    while (l < L[i]) shrink_l(l++);
    while (r > R[i]) shrink_r(r--);
    while (t < i) extend_t(++t);
    while (t > i) shrink_t(t--);
    ans[i] = s;
  }

  for (int i = 0; i < q; i++) {
    if (type[i] == 1) {
      printf("%lld\n", ans[i]);
    }
  }
}