14304: 【原4304】卖蘑菇的小姑娘
题目
题目描述
author: DS-TA Group2020 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/4304
Description
从前，有一个卖蘑菇的小女孩，她开了一家蘑菇店。最近，她决定开始记账，并希望你帮帮她。
已知她总共有N个篮筐用来装蘑菇。起初，每个篮筐里有$a_i$个蘑菇，之后她会采新的蘑菇放到某一个筐里，也会从某一个筐里卖出几个蘑菇，这些都需要你帮忙记下来。而且经过一段时间以后，她会想要知道某几个筐里总共有多少蘑菇。
Input Format
第一行一个整数N(N $\leq$ 100000)，表示有N个篮筐。 接下来有N个整数，代表一开始每个篮筐里有多少蘑菇。 接下来给你指令数M(M $\leq$ 100000)，代表后面有多少个指令。 最后是M行指令，共有三种： （1）GET i j：小姑娘进货了，第i个篮筐多了j个蘑菇； （2）SELL i j：某位顾客从第i个篮筐买走了j个蘑菇； （3）QUERY a b：小姑娘想知道第a到b个篮筐里总共有多少蘑菇（闭区间）。
Output Format
对于每个QUERY操作，输出一个整数i，表示区间里蘑菇总数（不超过int的范围）。
Sample Input
10
3 9 7 6 9 2 6 2 10 6
10
GET 3 2
SELL 4 9
SELL 9 8
GET 6 8
GET 9 7
SELL 5 9
SELL 3 1
QUERY 5 6
GET 2 7
QUERY 3 8
Sample Output
10
23
q4x3's solution
/**
* setment tree with lazy
* song gege nb!!!
**/
#include <iostream>
#include <stdio.h>
using namespace std;
const int N = 1e5 + 10;
int tree[N * 4], lazy[N * 4], a[N];
inline void read(int &x){
x = 0;
char ch;
bool f = 0;
while (ch = getchar(), (ch < '0' || ch > '9') && ch != '-');
if (ch == '-') f = 1;
else x = ch - '0';
while(ch = getchar(), ch >= '0' && ch <= '9') x = 10 * x + ch - '0';
x = f ? -x : x;
}
void build(int rt, int l, int r) {
if(l == r) {
// 叶子节点，递归返回
tree[rt] = a[l];
return;
}
int mid = (l + r) >> 1;
build(rt << 1, l, mid); // 递归建立左子树
build(rt << 1 | 1, mid + 1, r); // 递归建立右子树
tree[rt] = tree[rt << 1] + tree[rt << 1 | 1];
}
// 修改节点的权值和懒惰标记
void update(int rt, int l, int r, int w) {
tree[rt] += (r - l + 1) * w; // 更新节点的权值
lazy[rt] += w; // 更新节点的懒惰标记
}
// 将节点的懒惰标记下传给两个儿子
void pushdown(int rt, int l, int r) {
int mid = (l + r) >> 1;
update(rt << 1, l, mid, lazy[rt]); // 将懒惰标记下传给左儿子
update(rt << 1 | 1, mid + 1, r, lazy[rt]); // 将懒惰标记下传给右儿子
lazy[rt] = 0; // 懒惰标记清零
}
// 给区间[s, t]中每个数字都加上w
void modify(int rt, int l, int r, int s, int t, int w) {
if(s <= l && t >= r) { // 线段树节点区间[l, r]被区间[s, t]完全覆盖
update(rt, l, r, w);
return;
}
pushdown(rt, l, r); // 下传懒惰标记(先把钱还给儿子)
int mid = (l + r) >> 1;
if(s <= mid) modify(rt << 1, l, mid, s, t, w);
// s <= mid 说明区间[s, t]与左儿子[l, mid]区间有交
if(t > mid) modify(rt << 1 | 1, mid + 1, r, s, t, w);
// t > mid 说明区间[s, t]与右儿子[mid + 1, r]区间有交
tree[rt] = tree[rt << 1] + tree[rt << 1 | 1];
}
// 给第s个数加w
void modify_1(int rt, int l, int r, int s, int w) {
modify(rt, l, r, s, s, w);
}
int query(int rt, int l, int r, int s, int t) {
if(s <= l && t >= r) return tree[rt];
// 区间[s, t]完全覆盖线段树节点的区间[l, r]
int mid = (l + r) >> 1;
pushdown(rt, l, r);
if(t <= mid) return query(rt << 1, l, mid, s, t);
// 区间[s, t]与左儿子[l, mid]有交
else if(s > mid) return query(rt << 1 | 1, mid + 1, r, s, t);
// 区间[s, t]与右儿子[mid + 1, r]有交
else return query(rt << 1, l, mid, s, t)
+ query(rt << 1 | 1, mid + 1, r, s, t);
// 区间[s, t]同时与左儿子和右儿子有交
}
int n, m, tmp1, tmp2;
char tmp[10];
int main() {
read(n);
for(register int i = 1;i <= n;++ i) {
read(a[i]);
}
build(1, 1, n);
read(m);
for(register int i = 0;i < m;++ i) {
scanf("%s", tmp);
read(tmp1); read(tmp2);
if(tmp[0] == 'G') {
modify_1(1, 1, n, tmp1, tmp2);
} else if(tmp[0] == 'S') {
modify_1(1, 1, n, tmp1, - tmp2);
} else {
printf("%d\n", query(1, 1, n, tmp1, tmp2));
}
}
}
victrid's solution
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
long long seq[400005] = {};
long long read() {
long long x = 0;
bool w = 0;
char ch = 0;
while (ch < '0' || ch > '9') {
if (ch == '-')
w = 1;
ch = getchar();
}
while (ch >= '0' && ch <= '9') {
x = x * 10 + (ch - '0');
ch = getchar();
}
return w ? -x : x;
}
struct set {
int l;
int r;
int current;
long long& value;
set left() {
return set{l, (l + r) >> 1, current << 1, seq[current << 1]};
}
set right() {
return set{((l + r) >> 1) + 1, r, current << 1 | 1, seq[current << 1 | 1]};
}
bool isleaf() { return !(r - l); }
};
void buildtree(set s) {
if (s.isleaf()) {
s.value = read();
return;
}
buildtree(s.left());
buildtree(s.right());
s.value = s.left().value + s.right().value;
return;
}
long long query(int l, int r, set s) {
if (l <= s.l && s.r <= r) {
return s.value;
}
int mid = (s.l + s.r) >> 1;
long long q1 = 0, q2 = 0;
if (l <= mid) {
q1 = query(l, r, s.left());
}
if (r > mid) {
q2 = query(l, r, s.right());
}
return q1 + q2;
}
void update(int l, int r, set s) {
if (l < s.l || s.r < l) {
return;
}
if (s.isleaf()) {
s.value += r;
return;
}
int mid = (s.l + s.r) >> 1;
if (l <= mid) {
update(l, r, s.left());
} else {
update(l, r, s.right());
}
s.value = s.left().value + s.right().value;
return;
}
int main() {
//one group
int N, M;
N = read();
buildtree(set{1, N, 1, seq[1]});
M = read();
char a[30];
int l;
int r;
while (M--) {
scanf("%s", a);
l = read();
r = read();
switch (a[0]) {
case 'Q':
printf("%lld\n", query(l, r, set{1, N, 1, seq[1]}));
break;
case 'G':
update(l, r, set{1, N, 1, seq[1]});
break;
case 'S':
update(l, -r, set{1, N, 1, seq[1]});
break;
}
}
return 0;
}