今天刚试了一种新式写法:
好处是复用性比较好
坏处是代码稍微长点, 效率稍微差点把.
不过这种写法的优势大概没怎么体现吧.
做题的时候直接改模板方便些.
// luogu-judger-enable-o2
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
const int N = 500005;
template<typename Int>
struct BaseNode {
Int val, len, f;
BaseNode *ls, *rs;
BaseNode(Int _v = 0, BaseNode *_ls = nullptr,
BaseNode *_rs = nullptr, Int _f = 0, Int _len = 0):
val(_v), ls(_ls), rs(_rs), f(_f), len(_len) { }
void update() {
val = ls->val + rs->val;
}
void Merge(Int k) {
val += k * len, f += k;
}
void Down() {
if (f) ls->Merge(f), rs->Merge(f), f = 0;
}
};
#define new_Node() new Node()
template<typename Node, typename Int>
class Tree {
int n;
Node *root;
#define LS l, mid, node->ls
#define RS mid + 1, r, node->rs
template<typename Integar>
void build(int l, int r, Node *node, Integar *A) {
node->len = r - l + 1;
if (l == r) {
node->val = A[l];
return;
}
int mid = l + r >> 1;
node->ls = new_Node();
node->rs = new_Node();
build(LS, A), build(RS, A);
node->update();
}
void addition(int l, int r, Node *node, int L, int R, Int k) {
if (l >= L and r <= R) {
return node->Merge(k);
}
node->Down();
int mid = l + r >> 1;
if (L <= mid) addition(LS, L, R, k);
if (R > mid) addition(RS, L, R, k);
node->update();
}
Int Query(int l, int r, Node *node, int L, int R) {
if (l >= L and r <= R) {
return node->val;
}
node->Down();
int mid = l + r >> 1;
Int res = 0;
if (L <= mid) res += Query(LS, L, R);
if (R > mid) res += Query(RS, L, R);
return res;
}
public:
Tree(int _n) : n(_n), root(new_Node()) {}
template<typename Integar>
void build(Integar *A) {
build(1, n, root, A);
}
void addition(int L, int R, Int k) {
addition(1, n, root, L, R, k);
}
Int Query(int L, int R) {
return Query(1, n, root, L, R);
}
};
int A[N];
int main () {
int n, m;
scanf("%d%d", &n, &m);
Tree<BaseNode<long long>, long long>* T =
new Tree<BaseNode<long long>, long long>(n);
for (int i = 1; i <= n; i += 1) scanf("%d", &A[i]);
T->build(A);
while (m--) {
int opt, x, y, k;
scanf("%d%d%d", &opt, &x, &y);
if (opt == 1) {
scanf("%d", &k);
T->addition(x, y, k);
} else {
printf("%lld
", T->Query(x, y));
}
}
return 0;
}