Skip to content

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