MnZn刚学OI求助

WOERDESUGX @ 2022-11-22 19:24:06

#include<bits/stdc++.h>
using namespace std;
struct node{
    int l,r,la;
    long long ans;
    node() { l=r=ans=la=0; }
}a[154514];
long long Nt[154514];
int l,r,j,op,n,m;
inline void update(int k) {
    a[k].ans=a[k*2].ans+a[k*2+1].ans;
}
void build(int k,int l,int r)
{
    a[k].l=l;
    a[k].r=r;
    if(l==r) {
        a[k].ans=Nt[l];
        return ;
    }
    int mid=(l+r)/2;
    build(k*2,l,mid);
    build(k*2+1,mid+1,r);
    update(k);
}
void qj(int k,int l,int r,int x)
{
    if(a[k].l==l&&a[k].r==r) {
        a[k].ans+=(r-l+1)*x;
        a[k].la+=x;
        return ;
    }
    int mid=(a[k].l+a[k].r)>>1;
    if(r<=mid) qj(k*2,l,r,x);
    else if(l>mid) qj(k*2+1,l,r,x);
    else qj(k*2,l,mid,x),qj(k*2+1,mid+1,r,x);
    update(k);
}
void pushdown(int k)
{
    if(a[k].l==a[k].r) { a[k].la=0;return ; }
    a[k*2].ans+=(a[k*2].r-a[k*2].l+1)*a[k].la;
    a[k*2+1].ans+=(a[k*2+1].r-a[k*2+1].l+1)*a[k].la;
    a[k*2].la+=a[k].la;
    a[k*2+1].la+=a[k].la;
    a[k].la=0;
}
long long query(int k,int l,int r)
{
    if(a[k].la) pushdown(k);
    if(a[k].l==l&&a[k].r==r) return a[k].ans;
    int mid=(a[k].l+a[k].r)>>1;
    if(r<=mid) return query(k*2,l,r);
    else if(l>mid) return query(k*2+1,l,r);
    else return query(k*2,l,mid)+query(k*2+1,mid+1,r);
}
inline long long read()
{
    long long x=0;int f=1;char c=getchar();
    while(c<'0'||c>'9') {
        if(c=='-') f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9') {
        x=x*10+c-48;
        c=getchar();
    }
    return x*f;
}
int main()
{
    n=read();m=read();
    for(int i=1;i<=n;++i) Nt[i]=read();
    build(1,1,n);
    while(m--) {
        op=read(),l=read(),r=read();
        if(op==1) {
            j=read();
            qj(1,l,r,j);
        }
        else if(op==2) printf("%lld\n",query(1,l,r));
    }
    return 0;
}

by ZepX_D @ 2022-11-22 19:34:20

您卷死力

by WOERDESUGX @ 2022-11-22 19:35:15

@ZepX_D 没您强

by WOERDESUGX @ 2022-11-22 19:35:50

@ZepX_D

可我只是想学个线段树啊喂

by ZepX_D @ 2022-11-22 19:37:45

#include<bits/stdc++.h>
using namespace std;
struct node{
    int l,r,la;
    long long ans;
    // node() { l=r=ans=la=0; }
}a[154514<<2];
long long Nt[154514];
int l,r,j,op,n,m;
inline void update(int k) {
    a[k].ans=a[k*2].ans+a[k*2+1].ans;
}
void build(int k,int l,int r)
{
    a[k].l=l;
    a[k].r=r;
    if(l==r) {
        a[k].ans=Nt[l];
        return ;
    }
    int mid=(l+r)/2;
    build(k*2,l,mid);
    build(k*2+1,mid+1,r);
    update(k);
}
void pushdown(int k)
{
    if(a[k].l==a[k].r) { a[k].la=0;return ; }
    a[k*2].ans+=(a[k*2].r-a[k*2].l+1)*a[k].la;
    a[k*2+1].ans+=(a[k*2+1].r-a[k*2+1].l+1)*a[k].la;
    a[k*2].la+=a[k].la;
    a[k*2+1].la+=a[k].la;
    a[k].la=0;
}
void qj(int k,int l,int r,int x)
{
    if(a[k].l==l&&a[k].r==r) {
        a[k].ans+=(r-l+1)*x;
        a[k].la+=x;
        return ;
    }
    if (a[k].la) pushdown(k);
    int mid=(a[k].l+a[k].r)>>1;
    if(r<=mid) qj(k*2,l,r,x);
    else if(l>mid) qj(k*2+1,l,r,x);
    else qj(k*2,l,mid,x),qj(k*2+1,mid+1,r,x);
    update(k);
}
long long query(int k,int l,int r)
{
    if(a[k].la) pushdown(k);
    if(a[k].l==l&&a[k].r==r) return a[k].ans;
    int mid=(a[k].l+a[k].r)>>1;
    if(r<=mid) return query(k*2,l,r);
    else if(l>mid) return query(k*2+1,l,r);
    else return query(k*2,l,mid)+query(k*2+1,mid+1,r);
}
inline long long read()
{
    long long x=0, f=1;char c=getchar();
    while(c<'0'||c>'9') {
        if(c=='-') f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9') {
        x=x*10+c-48;
        c=getchar();
    }
    return x*f;
}
int main()
{
    n=read();m=read();
    for(int i=1;i<=n;++i) Nt[i]=read();
    build(1,1,n);
    while(m--) {
        op=read(),l=read(),r=read();
        if(op==1) {
            j=read();
            qj(1,l,r,j);
        }
        else if(op==2) printf("%lld\n",query(1,l,r));
    }
    return 0;
}

修改也要下放lazy，开四倍空间

by WOERDESUGX @ 2022-11-22 19:42:54

@ZepX_D 谢谢您

by ZepX_D @ 2022-11-22 19:44:30

@WOERDESUGX 您太强了，我去年打完比赛到今天五月才学线段树，您踩爆我

by LJKX @ 2022-11-22 19:46:23

太卷力%%%

by WOERDESUGX @ 2022-11-22 19:48:11

@ZepX_D .....

by WOERDESUGX @ 2022-11-22 19:48:35

@Kaedehara

同%

by whitenightdaye @ 2022-11-22 20:43:48

卷%%%%%%%