简化版题意：有 n 个数，初始值为 0，进行 m 次操作，每次操作支持将 [l, r] 加 v 和查询 [l, r] 中所有的数的和
n <= 1e9，m <= 1e3
博主 zz 的打了一个支持分裂节点的 splay，AC 后发现可以 m 方暴力过
方法和方伯伯的OJ这题类似，可以参考它的做法
#includeusing namespace std;typedef unsigned long long ull;typedef long long ll;template inline void read(T &f) { f = 0; T fu = 1; char c = getchar(); while(c < '0' || c > '9') {if(c == '-') fu = -1; c = getchar();} while(c >= '0' && c <= '9') {f = (f << 3) + (f << 1) + (c & 15); c = getchar();} f *= fu;}struct Node { ll val, tag, sum; int l, r, size; Node *ch[2]; Node () { val = tag = l = r = size = 0; ch[0] = ch[1] = NULL; }}*root;int n, m;void update(Node *u) { u -> size = u -> r - u -> l + 1; u -> val = u -> sum; if(u -> ch[0]) u -> size += u -> ch[0] -> size, u -> val += u -> ch[0] -> val; if(u -> ch[1]) u -> size += u -> ch[1] -> size, u -> val += u -> ch[1] -> val;}void pushdown(Node *u) { if(u -> tag) { if(u -> ch[0]) { u -> ch[0] -> tag += u -> tag; u -> ch[0] -> sum += (ll)(u -> ch[0] -> r - u -> ch[0] -> l + 1) * u -> tag; u -> ch[0] -> val += (ll)u -> ch[0] -> size * u -> tag; } if(u -> ch[1]) { u -> ch[1] -> tag += u -> tag; u -> ch[1] -> sum += (ll)(u -> ch[1] -> r - u -> ch[1] -> l + 1) * u -> tag; u -> ch[1] -> val += (ll)u -> ch[1] -> size * u -> tag; } u -> tag = 0; }}void rotate(Node *&u, int d) { Node *tmp = u -> ch[d]; u -> ch[d] = tmp -> ch[d ^ 1]; tmp -> ch[d ^ 1] = u; update(u); update(tmp); u = tmp;}void splay(Node *&u, int k) { if(u == NULL) return; pushdown(u); int ltree = u -> ch[0] ? u -> ch[0] -> size : 0; if(k > ltree && ltree + (u -> r - u -> l + 1) >= k) return; int d = k > ltree; splay(u -> ch[d], d ? k - ltree - (u -> r - u -> l + 1) : k); rotate(u, d);}void split(Node *&u, int x) { splay(u, x); ll sum = u -> sum; int l = u -> l, r = u -> r; if(u -> l != x) { Node *tmp = new Node(); tmp -> sum = sum / (ll)(r - l + 1) * (x - l); tmp -> l = l, tmp -> r = x - 1; tmp -> ch[0] = u -> ch[0]; update(tmp); u -> ch[0] = tmp; u -> l = x; } if(u -> r != x) { Node *tmp = new Node(); tmp -> sum = sum / (ll)(r - l + 1) * (ll)(r - x); tmp -> l = x + 1, tmp -> r = r; tmp -> ch[1] = u -> ch[1]; update(tmp); u -> ch[1] = tmp; u -> r = x; } u -> sum /= (ll)(r - l + 1); update(u);}int main() { cin >> n >> m; root = new Node(); root -> val = root -> tag = root -> sum = 0; root -> l = 1, root -> r = n; root -> size = n; root -> ch[0] = root -> ch[1] = NULL; for(int i = 1; i <= m; i++) {// printf("root -> size = %d\n", root -> size); int t; read(t); if(t == 1) { int a, b; ll c; read(a); read(b); read(c); if(a == 1 && b == n) { root -> val += (ll)n * c; root -> tag += c; root -> sum += (ll)(root -> r - root -> l + 1) * c; } else if(a == 1) { split(root, b + 1); root -> ch[0] -> val += (ll)root -> ch[0] -> size * c; root -> ch[0] -> tag += c; root -> ch[0] -> sum += (ll)(root -> ch[0] -> r - root -> ch[0] -> l + 1) * c; update(root); } else if(b == n) { split(root, a - 1); root -> ch[1] -> val += (ll)root -> ch[1] -> size * c; root -> ch[1] -> tag += c; root -> ch[1] -> sum += (ll)(root -> ch[1] -> r - root -> ch[1] -> l + 1) * c; update(root); } else { split(root, b + 1); split(root -> ch[0], a - 1); root -> ch[0] -> ch[1] -> val += (ll)root -> ch[0] -> ch[1] -> size * c; root -> ch[0] -> ch[1] -> tag += c; root -> ch[0] -> ch[1] -> sum += (ll)(root -> ch[0] -> ch[1] -> r - root -> ch[0] -> ch[1] -> l + 1) * c; update(root -> ch[0]); update(root); } } if(t == 2) { int a, b; read(a); read(b); if(a == 1 && b == n) { printf("%lld\n", root -> val); } else if(a == 1) { split(root, b + 1); printf("%lld\n", root -> ch[0] -> val); } else if(b == n) { split(root, a - 1); printf("%lld\n", root -> ch[1] -> val); } else { split(root, b + 1); split(root -> ch[0], a - 1); printf("%lld\n", root -> ch[0] -> ch[1] -> val); } } } return 0;}