P2357 守墓人
题目描述
他把墓地分为主要墓碑和次要墓碑,主要墓碑只能有
而每个墓碑有一个初始的风水值,这些风水值决定了墓地的风水的好坏,所以守墓人需要经常来查询这些墓碑。
风水也不是不可变,除非遭遇特殊情况,已知在接下来的
-
将
这个区间所有的墓碑的风水值增加 。 -
将主墓碑的风水值增加
-
将主墓碑的风水值减少
-
统计
这个区间所有的墓碑的风水值之和 -
求主墓碑的风水值
输入格式
第一行,两个正整数
第二行,
接下来
输出格式
输出会有若干行,对
Solution
直接套线段树板子即可。
#define int long long
#define lc u<<1
#define rc u<<1|1
int a[200010];
struct Tree { //线段树
ll l, r, sum, add;
}tr[800010];
void pushup(ll u) { //上传
tr[u].sum = tr[lc].sum + tr[rc].sum;
}
void pushdown(ll u) { //下传
if (tr[u].add) {
tr[lc].sum += tr[u].add * (tr[lc].r - tr[lc].l + 1);
tr[rc].sum += tr[u].add * (tr[rc].r - tr[rc].l + 1);
tr[lc].add += tr[u].add;
tr[rc].add += tr[u].add;
tr[u].add = 0;
}
}
void build(ll u, ll l, ll r) { //建树
tr[u] = {l,r,a[l],0};
if (l == r) return;
ll m = l + r >> 1;
build(lc, l, m);
build(rc, m + 1, r);
pushup(u);
}
void change(ll u, ll l, ll r, ll k) { //区修
if (l <= tr[u].l && tr[u].r <= r) {
tr[u].sum += (tr[u].r - tr[u].l + 1) * k;
tr[u].add += k;
return;
}
ll m = tr[u].l + tr[u].r >> 1;
pushdown(u);
if (l <= m) change(lc, l, r, k);
if (r > m) change(rc, l, r, k);
pushup(u);
}
ll query(ll u, ll l, ll r) { //区查
if (l <= tr[u].l && tr[u].r <= r) return tr[u].sum;
ll m = tr[u].l + tr[u].r >> 1;
pushdown(u);
ll sum = 0;
if (l <= m) sum += query(lc, l, r);
if (r > m) sum += query(rc, l, r);
return sum;
}
void solve() {
int n, f;cin >> n >> f;
for (int i = 1;i <= n;i++)cin >> a[i];
int main = 0;
build(1, 1, n);
while (f--) {
int op;cin >> op;
if (op == 1) {
int l, r, k;cin >> l >> r >> k;change(1, l, r, k);
} else if (op == 2) {
int k;cin >> k;
main += k;
// change(1, 1, 1, k);
} else if (op == 3) {
int k;cin >> k;
main -= k;
// change(1, 1, 1, -k);
} else if (op == 4) {
int l, r;cin >> l >> r;
// cout << query(1, l, r) << "\n";
cout << query(1, l, r) + (l == 1) * main << "\n";
} else {
cout << query(1, 1, 1) + main << '\n';
// cout << query(1, 1, 1) << '\n';
}
}
}