RSQ and RAQ, mo's algorithm with update

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

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]);
}
}
}