9pts求调
查看原帖
9pts求调
759274
Stevehim楼主2023/2/7 18:57

QAQ

#include <cstdio>
#include <cstring>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <string>
#define maxn 1000010
using namespace std;
typedef long long ll; //开ll
/*
默写结构体线段树
范围为模板1-2
*/

inline int ls(int root) {
    return root << 1;
}
inline int rs(int root) {
    return root << 1 | 1;
}

struct node {
    int l;
    int r;
    ll val;
    ll tag = 0;
} a[maxn];
int n,m,opt,l,r,d,k,t;
int num[maxn]; //存放值的数组
int chafen[maxn];//存放差分数组
void build(int p, int l, int r) {
    a[p].l = l;
    a[p].r = r;
    if (l == r) {
        a[p].val = num[l];
        return;
    }
    int mid = (l + r) / 2;
    build(p * 2, l, mid); //建立左子树
    build(p * 2 + 1, mid + 1, r); //建立右子树
    a[p].val = a[p * 2].val + a[p * 2 + 1].val;
    return;
}

/*
spread函数的标注:
1.区间+1的原因:假设 1 2 3 4 5,我的l为1,r为5,那么我用r - l为4,会忽略掉一个端点
(其实根节点设为0有可能不会出错但是根节点设为零p*2会出错)
*/
void spread(int p,int l,int r) { //下传操作
    int mid = (l - r) / 2;
    a[ls(p)].tag += a[p].tag;
    a[rs(p)].tag += a[p].tag;
    a[ls(p)].val += (ll)a[p].tag *(mid - l +1);
    a[rs(p)].val += (ll)a[p].tag *(r - mid);
    a[p].tag = 0;
}

void change1(int p, int l, int r, ll z) {
    if (l <= a[p].l && r >= a[p].r) { //覆盖了
        a[p].tag += z;
        a[p].val += (ll)(a[p].r - a[p].l + 1) *z;
        return;
    }
    spread(p,a[p].l,a[p].r);
    int mid = (a[p].l + a[p].r) / 2; //注意:不是 l 与 r !!!
    if (l <= mid) {
        change1(p * 2, l, r, z);
    }
    if (r > mid) {
        change1(p * 2 + 1, l, r, z);
    }
    a[p].val = a[p * 2].val + a[p * 2 + 1].val; //加上值
}


ll ask(int p, int l, int r) {
    if (l <= a[p].l && r >= a[p].r) {
        return a[p].val;
    }
    spread(p,a[p].l,a[p].r);
    ll ans = 0;
    int mid = (a[p].l + a[p].r) / 2;
    if (l <= mid) {
        ans += ask(p * 2, l, r);
    }
    if (r > mid) {
        ans += ask(p * 2 + 1, l, r);
    }
    return ans;
}

int main() {
    freopen("P1438_2.in","r",stdin);
    cin >>n >> m;
    for(int i = 1; i <= n; i++) {
        cin >> num[i];
    }
    for(int i = n - 1; i > 0; i--) {
        num[i + 1] = num[i + 1] - num[i];
    }
    build(1,1,n);
    for(int i = 0; i < m; i++) {
        cin >> opt;
        if(opt == 1) {
            cin >> l >>r >> k >>d;
            change1(1,l,l,k);
            if(l + 1 <= r) {
                change1(1,l+1,r,d);
            }
            if(r < n) {
                change1(1,r+1,r+1,-(k+d*(r-l)));
            }

        } else {
            cin >> t;
            cout << ask(1,1,t) << endl;
        }
    }
    return 0;
}

2023/2/7 18:57
加载中...