不知道为什么wa了三个点

P3372 【模板】线段树 1

Exile_Code @ 2023-09-09 23:26:10

#define  _CRT_SECURE_NO_WARNINGS
#include <iostream>
using namespace std;
#include <vector>
#include <set>
#include <map>
#include <unordered_map>
#include <cstdio>
#include <cstring>
#include <queue>
#include <cstdlib>
#include <algorithm>
#include <list>
#include <string>
#include <cmath>
#include <bitset>
#include<stack>
using namespace std;
using ll = long long;
#define LF(x) fixed << setprecision(x)
typedef pair<int, int> pii;
#define endl "\n"
int n, w[100];
struct node { int l, r, sum, add; }tr[4 * 100];
//线段树
class Segment_tree {
    /*
        叶子节点储存元素本身,非叶子节点存储统计值,用来维护区间和,区间最值,区间GCD
        父节点的编号是p,左孩子的编号是2p,右孩子的编号是2p+1
    */
private:
#define lc p<<1
#define rc p<<1|1

public:

    //建树
    void build(int p, int l, int r) {
        tr[p] = { l,r,w[l] };//这个操作对于非叶子结点是没有意义的,因为在最后一步会进行更新
        if (r == l)return;
        int m = l + r >> 1;
        build(lc, l, m);
        build(rc, m + 1, r);//p<<2一定是一个偶数,偶数的末位是0,所以按位或1,相当于+1
        tr[p].sum = tr[lc].sum + tr[rc].sum;
    }

    //区间查询,拆分拼凑,如果查询区间完全覆盖掉当前的节点区间,就立刻返回当前的区间值 On
    int query(int p, int x, int y) {
        if (x <= tr[p].l && tr[p].r <= y)
            return tr[p].sum;
        int m = tr[p].l + tr[p].r >> 1;
        pushdown(p);
        int sum = 0;
        if (x <= m) sum += query(lc, x, y);
        if (y > m)      sum += query(rc, x, y);
        return sum;
    }

    //向上更新
    void pushup(int p) {
        tr[p].sum = tr[lc].sum + tr[rc].sum;
    }

    //下传懒标记
    void pushdown(int p) {
        if (tr[p].add) {
            tr[lc].sum += tr[p].add * (tr[lc].r - tr[lc].l + 1);
            tr[rc].sum += tr[p].add * (tr[rc].r - tr[rc].l + 1);
            tr[lc].add += tr[p].add;
            tr[rc].add += tr[p].add;
            tr[p].add = 0;
        }
    }

    //区间修改
    void update(int p, int x, int y, int k) {
        if (x <= tr[p].l && tr[p].r <= y) {//覆盖则修改
            tr[p].sum += (tr[p].r - tr[p].l + 1) * k;//宽度*k
            tr[p].add += k;
            return;
        }
        int m = tr[p].l + tr[p].r >> 1;
        pushdown(p);
        if (x <= m) update(lc, x, y, k);
        if (y > m)      update(rc, x, y, k);//不取等是因为,等于的情况已经在上一句修改了
        pushup(p);
    }//懒惰修改,当完全覆盖时就打上懒标记,下次需要的时候再下传懒标记 Ologn

    //点修改
    void update(int p, int x, int k) {
        if (tr[p].l == x && tr[p].r == x) {
            tr[p].sum += k;
            return;
        }

        int m = tr[p].l + tr[p].r >> 1;//判断这个点在那个子树上面
        if (x <= m)update(lc, x, k);
        else             update(rc, x, k);

        tr[p].sum = tr[lc].sum + tr[rc].sum;

    }
};

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n, m; cin >> n >> m;
    for (int i = 1; i <= n; i++)
        cin >> w[i];
    Segment_tree s;
    s.build(1,1,n);
    for (int i = 0; i < m; i++) {
        int q; cin >> q;
        if (q == 1) {
            int a, b,k; cin >> a >> b>>k;
            s.update(1, a, b, k);
        }
        else {
            int a, b; cin >> a >> b;
            cout << s.query(1, a, b) << endl;
        }

    }

    return 0;
}

by __HHX__ @ 2023-09-09 23:43:01

典,注意数据范围(不是线段树)


by __HHX__ @ 2023-09-09 23:47:22

建议看一下

对于 100\% 的数据:1 \leq n,m \leq 10^5

保证任意时刻数列中所有元素的绝对值之和 \leq 10^{18}


|