这颗线段树多好看呀
查看原帖
这颗线段树多好看呀
742017
zhangxiao666楼主2024/1/8 19:10

好看但写挂了。

过路大佬们帮忙调一调吧qwq

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 2e5 + 10;
int n, q;
int a[N];
int tr[4 * N], tag[4 * N];

int read()
{
    register int f = 1, s = 0; register char ch = getchar();
    while(ch < '0' || ch > '9') {if(ch == '-') f = -1; ch = getchar();}
    while(ch >= '0' && ch <= '9') {s = s * 10 + ch - '0'; ch = getchar();}
    return f * s;
}

void pushup(int x)
{
    tr[x] = tr[x << 1] + tr[x << 1 | 1]; 
}

void change(int x, int l, int r, int k)
{
    tr[x] += (r - l + 1) * k;
    tag[x] += k;
}

void pushdown(int x, int l, int r)
{
    int mid = l + r >> 1;
    change(x << 1, l, mid, tag[x]);
    change(x << 1 | 1, mid + 1, r, tag[x]);
    tag[x] = 0;
}

void build(int x, int l, int r)
{
    if(l == r) {tr[x] = a[l]; return;}
    int mid = l + r >> 1;
    build(x << 1, l, mid), build(x << 1 | 1, mid + 1, r);
    pushup(x);
}

void modify(int x, int l, int r, int ql, int qr, int k)
{
    if(ql <= l && r <= qr){change(x, l, r, k); return;}
    int mid = l + r >> 1;
    pushdown(x, l, r);
    if(ql <= mid) modify(x << 1, l, mid, ql, qr, k);
    if(mid < qr) modify(x << 1 | 1, mid + 1, r, ql, qr, k);
    pushup(x);
}

int query(int x, int l, int r, int ql, int qr)
{
    if(ql <= l && r <= qr) return tr[x];
    int ans = 0, mid = l + r >> 1;
    pushdown(x, l, r);
    if(ql <= mid) ans += query(x << 1, l, mid, ql, qr);
    if(mid < qr) ans += query(x << 1 | 1, mid + 1, r, ql, qr);
    return ans;
}

signed main()
{
    std::ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    n = read(), q = read();
    for(int i = 1; i <= n; i++) a[i] = read();
    build(1, 1, n);
    while(q--)
    {
        int op;
        op = read();
        if(op == 1) modify(1, 1, n, read(), read(), read());
        if(op == 2) modify(1, 1, n, 1, 1, read());
        if(op == 3) modify(1, 1, n, 1, 1, read() * (-1));
        if(op == 4) cout << query(1, 1, n, read(), read()) << "\n";
        if(op == 5) cout << query(1, 1, n, 1, 1) << "\n";
    }
    return 0;
}
2024/1/8 19:10
加载中...