蒟蒻线段树求调

rxc2021 @ 2022-08-17 16:16:27

#include<bits/stdc++.h>
#define N 10000086
#define int long long
using namespace std;
const int M=214748364700;
int n,m,a[N],dat[N],lazy[N],mul[N];
void build(int x,int l,int r) {
    if(l==r) {
        dat[x]=a[l];
        lazy[x]=0;
        mul[x]=-M;
        return;
    }
    int mid=(l+r)>>1;
    build(x*2,l,mid);
    build(x*2+1,mid+1,r);
    dat[x]=max(dat[x*2],dat[x*2+1]);
}
inline void down2(int x) {
    if(mul[x]!=-M) {
        lazy[x<<1]=lazy[x<<1|1]=0;
        mul[x<<1]=mul[x<<1|1]=mul[x];
        dat[x<<1]=dat[x<<1|1]=mul[x];
        mul[x]=-M;
    }
}
inline void down1(int x) {
    if(lazy[x]) {
        down2(x);
        dat[x<<1]+=lazy[x],dat[x<<1|1]+=lazy[x];
        lazy[x<<1]+=lazy[x],lazy[x<<1|1]+=lazy[x];
        lazy[x]=0;
    } 
}
inline void pushdown(int x) {
    down2(x),down1(x);  
}
inline void Change1(int L,int R,int l,int r,int x,int p) {//+
    if(L<=l&&R>=r) {
        down2(x);
        dat[x]+=p;
        lazy[x]+=p;
        return;
    }
    pushdown(x);
    int mid=(l+r)>>1;
    if(L<=mid)Change1(L,R,l,mid,x<<1,p);
    if(R>mid)Change1(L,R,mid+1,r,x<<1|1,p);
    dat[x]=max(dat[x<<1],dat[x<<1|1]);
}
inline void Change2(int L,int R,int l,int r,int x,int p) {
    if(L<=l&&R>=r){
        lazy[x]=0;
        dat[x]=p;
        mul[x]=p;
        return;
    }
    pushdown(x);
    int mid=(l+r)>>1;
    if(L<=mid)Change2(L,R,l,mid,x<<1,p);
    if(R>mid)Change2(L,R,mid+1,r,x<<1|1,p);
    dat[x]=max(dat[x<<1],dat[x<<1|1]);
}
int qjck(int L, int R, int l, int r, int p) {
    if(L<=l&&r<=R) return dat[p];
    int mid=(l+r)>>1, res=-M;
    if(mid>=L)res=max(res, qjck(L,R,l,mid,p<<1));
    if(mid<=R)res=max(res, qjck(L,R,mid+1,r,p<<1|1));
    return res;
}
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);  
    cin>>n>>m;
    for(int i=1; i<=n; i++)
        cin>>a[i];
    build(1,1,n);
    for (int i = 1;i <= n * 4; ++ i) mul[i] = -M;
    for(int j=1; j<=m; j++) {
        int s,x,y,k;
        cin>>s>>x>>y;
        if(s==3) {
            cout<<qjck(1,n,x,y,1)<<'\n';
        } 
        else {
            cin>>k;
            if(s==1)Change2(1,n,x,y,1,k);
            else Change1(1,n,x,y,1,k);
        }
    }
    return 0;
}

by ZHANGGUIZHI @ 2022-08-17 16:28:07

把

if(L<=l&&R>=r) {
        down2(x);
        dat[x]+=p;
        lazy[x]+=p;
        return;
    }

里的down2(x)去掉

把pushdown合并成

inline void pushdown(int x) {
    if(mul[x]!=-M) {
        lazy[x<<1]=lazy[x<<1|1]=0;
        mul[x<<1]=mul[x<<1|1]=mul[x];
        dat[x<<1]=dat[x<<1|1]=mul[x];
        mul[x]=-M;
    }
    if(lazy[x]）{
dat[x<<1]+=lazy[x],dat[x<<1|1]+=lazy[x];
  lazy[x<<1]+=lazy[x],lazy[x<<1|1]+=lazy[x];
        lazy[x]=0;
    } 
}

会不会更好一点

by 上杉越 @ 2022-08-17 16:52:00

emmm

by Chagely_Z @ 2022-08-17 17:27:37

贴贴

#include<bits/stdc++.h>
#define N 10000086
#define int long long
using namespace std;
const int M=214748364700;
int n,m,a[N];
struct node{
    int l,r,dat,lazy,mul;
}s[N*4+2];
void build(int q,int l,int r){
    s[q].l=l,s[q].r=r,s[q].lazy=0,s[q].mul=-M;
    if(l==r){
        s[q].dat=a[l];
        return;
    }
    int mid=(l+r)/2;
    build(q*2,l,mid);
    build(q*2+1,mid+1,r);
    s[q].dat=max(s[q*2].dat,s[q*2+1].dat);
}
void tip1(int q,int x){
    s[q].dat+=x;
    if(s[q].mul!=-M) s[q].mul+=x;
    else s[q].lazy+=x;
}
void tip2(int q,int x){
    s[q].mul=x;
    s[q].dat=x;
    s[q].lazy=0;
}
void down1(int q){
    if(s[q].lazy!=0){
        tip1(q*2,s[q].lazy);
        tip1(q*2+1,s[q].lazy);
        s[q].lazy=0;
    }
}
void down2(int q){
    if(s[q].mul!=-M){
        tip2(q*2,s[q].mul);
        tip2(q*2+1,s[q].mul);
        s[q].mul=-M;
    }
}
void pushdown(int x){
    down1(x),down2(x);
}
inline void Change1(int q,int l,int r,int p){
    if(s[q].l>=l&&s[q].r<=r){
        tip1(q,p);
        return;
    }
    pushdown(q);
    int mid=(s[q].l+s[q].r)/2;
    if(l<=mid)Change1(q*2,l,r,p);
    if(r>mid)Change1(q*2+1,l,r,p);
    s[q].dat=max(s[q*2].dat,s[q*2+1].dat);
}
inline void Change2(int q,int l,int r,int p) {
    if(s[q].l>=l&&s[q].r<=r){
        s[q].lazy=0;
        s[q].mul=p;
        s[q].dat=p;
        return;
    }
    pushdown(q);
    int mid=(s[q].l+s[q].r)/2;
    if(l<=mid)Change2(q*2,l,r,p);
    if(r>mid)Change2(q*2+1,l,r,p);
    s[q].dat=max(s[q*2].dat,s[q*2+1].dat);
}
int qjck(int q,int l,int r) {
    if(s[q].l>=l&&s[q].r<=r) return s[q].dat;
    pushdown(q);
    int mid=(s[q].l+s[q].r)/2, res=-M;
    if(l<=mid) res=max(res, qjck(q*2,l,r));
    if(r>mid) res=max(res, qjck(q*2+1,l,r));
    return res;
}
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);  
    cin>>n>>m;
    for(int i=1; i<=n; i++) cin>>a[i];
    build(1,1,n);
    for(int i=1; i<=m; i++) {
        int s,x,y,k;
        cin>>s>>x>>y;
        if(s==3){
            cout<<qjck(1,x,y)<<'\n';
        } 
        else {
            cin>>k;
            if(s==1)Change2(1,x,y,k);
            else Change1(1,x,y,k);
        }
    }
    return 0;
}