寂寞女大学生刚学OI0.01ms,线段树+差分求调
查看原帖
寂寞女大学生刚学OI0.01ms,线段树+差分求调
713343
Naganorhara_Yoimiya楼主2024/11/23 21:01
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5+10;
int n,m,a[maxn+10],input[maxn+10];

struct Segment_Tree{
    int tree[(maxn<<2)+10],lazy[(maxn<<2)+10];
    void pushup(int i){
        tree[i] = tree[i<<1] + tree[i<<1|1];
    }
    void build(int k,int l,int r){
        if(l == r){
            tree[k] = a[l];
            return;
        }
        lazy[k] = 0;
        int mid = l + ((r - l) >> 1);
        build(k<<1,l,mid);
        build(k<<1|1,mid+1,r);
		pushup(k);
    }
    void pushdown(int i,int l,int r){
        lazy[i<<1] += lazy[i];
        lazy[i<<1|1] += lazy[i];
        int mid = l + ((l+r) >> 1);
        tree[i<<1] += lazy[i] * (mid - l + 1);
        tree[i<<1|1] += lazy[i] * (r - mid);
        lazy[i] = 0;
    }
    void update(int l,int r,int k,int L,int R,int v){
        if(L <= l && r <= R){
            tree[k] += v * (r - l + 1);
            lazy[k] += v;
            return;
        }
        pushdown(k,l,r);
        int mid = l + ((r - l) >> 1);
        if(l <= mid) update(l,r,k<<1,L,mid,v);
        if(mid < r) update(r,r,k<<1|1,mid+1,R,v);
    }
    int query(int l,int r,int k,int L,int R){
        if(L <= l && r <= R){
            return tree[k];
        }
        pushdown(k,l,r);
        int res = 0;
        int mid = l + ((r - 1) >> 1);
        if(l <= mid) res += query(l,r,k<<1,L,mid);
        if(mid < r) res += query(l,r,k<<1|1,mid+1,r);
        return res;
    }
} t;

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	cin >> n >> m;
	for(int i = 1,x;i <= n;i++){
        cin >> input[i];
    }
    a[1] = input[1];
    for(int i = 2;i <= n;i++) a[i] = input[i] - input[i-1];
    t.build(1,1,n);
    for(int i = 1,op,l,r,k,d;i <= m;i++){
        cin >> op >> l;
        if(op == 1){
            cin >> r >> k >> d;
            t.update(l,l,1,1,n,k);
            t.update(l+1,r,1,1,n,d);
            t.update(r+1,r+1,1,1,n,-(k+d*(r-l)));
        }else{
            cout << t.query(1,l,1,1,n) << '\n';
        }
    }
	return 0;
} 
2024/11/23 21:01
加载中...