蒟蒻线段树求调

P1253 扶苏的问题

_pharos_C @ 2023-04-10 13:29:30

不知道线段树哪里有问题?10pts

#include<bits/stdc++.h>
#define ll long long
#define maxn 1000001
using namespace std;
ll ans[maxn<<2], lazy[maxn<<2];
ll a[maxn];

void Sum(ll x) {
    ans[x] = ans[x<<1] + ans[(x<<1)|1];
}

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

void update1(int l, int r, int s, int t, ll x, int c) {
    if(l<=s and t<=r) {
        ans[x] += (t-s+1) * c;
        lazy[x] += c;
        return;
    }
    int mid=(s+t)>>1;
    if(lazy[x] and s!=t) {
        ans[x<<1] += (mid-s+1) * lazy[x];
        ans[(x<<1)|1] += (t-mid) * lazy[x];
        lazy[x<<1] += lazy[x];
        lazy[(x<<1)|1] += lazy[x];
        lazy[x] = 0;
    }
    if(l<=mid) update1(l, r, s, mid, x<<1, c);
    if(r>mid) update1(l, r, mid+1, t, (x<<1)|1, c);
    Sum(x);
}

void update2(int l, int r, int s, int t, ll x, int c) {
    if(l<=s and t<=r) {
        ans[x] = (t-s+1) * c;
        lazy[x] = c;
        return;
    }
    int mid=(s+t)>>1;
    if(lazy[x] and s!=t) {
        ans[x<<1] = c * (mid-s+1);
        ans[(x<<1)|1] = c * (t-mid);
        lazy[x<<1] = lazy[(x<<1)|1] = c;
    } 
    if(l<=mid) update2(l, r, s, mid, x<<1, c);
    if(r>mid) update2(l, r, mid+1, t, (x<<1)|1, c);
    Sum(x);
}

ll getsum(int l, int r, int s, int t, ll x) {
    if(l<=s and t<=r) {
        return ans[x];
    }
    int mid=(s+t)>>1;
    if(lazy[x]) {
        ans[x<<1] += lazy[x] * (mid-s+1);
        ans[(x<<1)|1] += lazy[x] * (t-mid);
        lazy[x<<1] += lazy[x];
        lazy[(x<<1)|1] += lazy[x];
        lazy[x] = 0;
    }
    ll sum = 0;
    if(l<=mid) sum = getsum(l, r, s, mid, x<<1);
    if(r>mid) sum += getsum(l, r, mid+1, t, (x<<1)|1);
    return sum;
}

int n, q;
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin >> n >> q;
    for(int i=1; i<=n; i++) {
        cin >> a[i];
    }
    build(1, n, 1);
    for(int i=1, opt, l, r, x; i<=q; i++) {
        cin >> opt;
        if(opt==1) {
            cin >> l >> r >> x;
            update2(l, r, 1, n, 1, x);
        }
        if(opt==2) {
            cin >> l >> r >> x;
            update1(l, r, 1, n, 1, x);
        }
        if(opt==3) {
            cin >> l >> r;
            cout << getsum(l, r, 1, n, 1) << endl;
        }
    }
    return 0;
}

by seanlsy @ 2023-04-10 13:35:48

建议 #define int long long 试试


by _pharos_C @ 2023-04-20 15:54:01

@seanlsy 仍然不行


|