91pts 警示后人
查看原帖
91pts 警示后人
736527
Arrtan_73楼主2024/4/6 09:23
#include<bits/stdc++.h>
using namespace std;
#define MAXN 100005
#define ll long long
const long long inf = -2e18 - 5; 
ll n, m, a[MAXN], ans[MAXN << 2], tag[MAXN << 2];
inline ll ls(ll x){
    return x << 1;
}
inline ll rs(ll x){
    return x << 1 | 1;
}
inline void push_up(ll p){
    ans[p] = ans[ls(p)] + ans[rs(p)];
}
void scan(){
    scanf("%lld%lld", &n, &m);
    for(int i = 1; i <= n; i++)scanf("%lld", &a[i]);
}
void build(ll p,ll l,ll r){
    if(l == r){ans[p] = a[l] - a[l - 1];return;}
    ll mid = (l + r) >> 1;
    build(ls(p), l, mid);
    build(rs(p), mid+1, r);
    push_up(p);
}
inline void f(ll p,ll l,ll r,ll k){
    tag[p] = tag[p] + k;
    ans[p] = ans[p] + (r - l + 1) * k;
}
inline void push_down(ll p,ll l,ll r){
    ll mid = (l + r) >> 1;
    f(ls(p), l, mid, tag[p]);
    f(rs(p), mid+1, r, tag[p]);
    tag[p] = 0;
}
inline void update(ll nl,ll nr,ll l,ll r,ll p, ll k){
    if(nl <= l && r <= nr){
    	tag[p] = tag[p] + k;
    	ans[p] = ans[p] + (r - l + 1) * k;
        return;
    }
    push_down(p, l, r);
    ll mid = (l + r)  >> 1;
    if(nl <= mid)update(nl, nr, l, mid, ls(p), k);
    if(nr > mid)update(nl, nr, mid+1, r, rs(p), k);
    push_up(p);
}
ll query(ll q_x,ll q_y,ll l,ll r,ll p){
    ll res = 0;
    if(q_x <= l && r <= q_y)return ans[p];
    ll mid = (l + r) >> 1;
    push_down(p, l, r);
    if(q_x <= mid)res = res + query(q_x, q_y, l, mid, ls(p));
    if(q_y > mid)res = res + query(q_x, q_y, mid+1, r, rs(p));
    return res;
}
int main(){
	scan();
	build(1, 1, n);
	while(m--){
		ll kind, l, r, k, d;
		scanf("%lld", &kind);
		if(kind == 1){
			scanf("%lld%lld%lld%lld", &l, &r, &k, &d);
			if(l != n)update(l + 1, r, 1, n, 1, d);
			update(l, l, 1, n, 1, k);
			if(r != n)update(r + 1, r + 1, 1, n, 1, -(k + d * (r - l)));
		}
		else{
			scanf("%lld", &l);
			printf("%lld\n", query(1, l, 1, n, 1));
		}
	}
	return 0;
}

看下面两行

if(l != n)update(l + 1, r, 1, n, 1, d);
			update(l, l, 1, n, 1, k);
			if(r != n)update(r + 1, r + 1, 1, n, 1, -(k + d * (r - l)));

这里r,l必须特判越界情况,否则只有82,09pts,

我就挂在这了,调了很久

2024/4/6 09:23
加载中...