只有样例1AC
查看原帖
只有样例1AC
1057425
jofish楼主2024/11/2 02:08

求助,只有样例1AC

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const int N =1e6+3;
#define lp p<<1
#define rp p<<1|1
struct node {
    int l, r;
    ll x, tag;
    ll mid() const {return l + r >> 1;}
    bool inquery(int _l, int _r) const{ return l >= _l && r <= _r;}
    bool islev() const {return l == r;}
    ll len() const {return r-l+1;}
}tr[4*N];

int n, m, op;
ll x, y, k, d;
ll arr[N], o[N];

void up(int p) {
    tr[p].x = tr[lp].x + tr[rp].x;
}

void down(int p) {
    if (!tr[p].tag) return;
    tr[lp].x += tr[lp].len()*tr[p].tag;
    tr[rp].x += tr[rp].len()*tr[p].tag;
    tr[lp].tag += tr[p].tag;
    tr[rp].tag += tr[p].tag;
    tr[p].tag = 0;
}

void build(int l=1, int r=n+1, int p=1) {
    tr[p] = {l, r, arr[l], 0};
    if (l==r) return;
    int mid = l + r >> 1;
    build(l, mid, lp);
    build(mid+1, r, rp);
    up(p);
}

void fix(int l, int r, ll val, int p=1) {
    if (tr[p].inquery(l, r)) {
        tr[p].x += tr[p].len() * val;
        tr[p].tag += val;
        return;
    }
    down(p);
    if (tr[p].mid() >= l) fix(l, r, val, lp);
    if (tr[p].mid() < r) fix(l, r, val, rp);
    up(p);
}

ll query(int l, int r, int p = 1) {
    if (tr[p].inquery(l, r)) return tr[p].x;
    ll res = 0;
    down(p);
    if (tr[p].mid() >= l) res += query(l, r, lp);
    if (tr[p].mid() < r) res += query(l, r, rp);
    return res;
}


int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin>>n>>m;
    for (int i=1; i<=n; i++) cin>>o[i];
    for (int i=1; i<=n; i++) arr[i] = o[i] - o[i-1];
    build();
    while(m--) {
        cin>>op;
        if (op == 1) {
            cin>>x>>y>>k>>d;
            fix(x,x,k);
            if (x < y)fix(x+1, y, d);
            if (x <= n)fix(y+1, y+1, -(k + d*(y-1)));
        }
        else {
            cin>>x;
            cout<<query(1, x)<<"\n";
        }

    }


}
2024/11/2 02:08
加载中...