蒟蒻爆零线段树求调
查看原帖
蒟蒻爆零线段树求调
804794
NPCaaabc楼主2023/10/17 21:48
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
int n,m;
ll t[114514];
ll w[414514];
ll lzyA[414514],lzyD[414514];
ll S(int u,int l,int r,int k,int d){ //求等差数列和
    return (2*k+d*(r-l)) * (r-l+1) / 2;
}
void build(int u,int l,int r){ //建树
    if(l==r) {
        w[u] = t[l];
        return;
    }
    int mid = (l+r) / 2;
    build(u*2,l,mid);
    build(u*2+1,mid+1,r);
}
void addTag(int u,int l,int r,int k,int d){//加 tag
    w[u] += S(u,l,r,k,d);
    lzyA[u] += k;
    lzyD[u] += d;
}
void pushDown(int u,int l,int r){// 下传 tag
    int mid = (l+r) / 2;
    int k = lzyA[u],d = lzyD[u];
    addTag(u*2,l,mid,k,d);
    int HalfLen = mid - l + 1;
    addTag(u*2+1,mid+1,r,k+d*HalfLen-d,d);
    lzyA[u] = lzyD[u] = 0;
}

ll findP(int u,int l,int r,int p){// 查询点
    pushDown(u,l,r);
    if(l==r) return w[u];
    int mid = (l+r)/2;
    if(p <= mid) return findP(u*2,l,mid,p);
    else return findP(u*2+1,mid+1,r,p); 
}
bool inRange(int l,int r,int L,int R){
    return (L<=l) && (r<=R);
}
bool outRange(int l,int r,int L,int R){
    return (R<l) || (r<L);
}
void modifyR(int u,int l,int r,int L,int R,int k,int d){ // 修改区间
    if(outRange(l,r,L,R)) return;
    if(inRange(l,r,L,R)) {
        addTag(u,l,r,k,d);
        return;
    }
    int mid = (l+r) / 2;
    modifyR(u*2,l,mid,L,R,k,d);
    modifyR(u*2+1,mid+1,r,L,R,k+d*(mid-l),d);
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        scanf("%lld",&t[i]);
    }
    build(1,1,n);
    while(m--){
        int opt;scanf("%d",&opt);
        if(opt == 1) {
            int L,R,k,d;scanf("%d%d%d%d",&L,&R,&k,&d);
            modifyR(1,1,n,L,R,k,d);
        }
        if(opt == 2) {
            int p;scanf("%d",&p);
            printf("%lld\n",findP(1,1,n,p));
        }

    }
    return 0;
}
2023/10/17 21:48
加载中...