线段树板子全RE求调,目测数组大小无误

P3372 【模板】线段树 1

Yang818 @ 2023-10-20 19:13:24

#include<bits/stdc++.h>
#define F(_b,_e) for(int i=_b;i<=_e;i++)
#define int long long
using namespace std;

inline int read(){
    int f=1,x=0;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
    return f*x;
}
void write(int x) {
    if(x<0) putchar('-'),x=-x;
    if(x>9) write(x/10);
    putchar(x%10+'0');
}
const int MAXN=2e5+5;
struct Seg_tree{
    int l,r;
    long long val,tag;
}t[MAXN<<2];
int a[MAXN],n,m; 

void build(int pos,int left,int right){
    t[pos].l=left;
    t[pos].r=right;
    if(left==right){
        t[pos].val=a[left];
        return;
    }
    int mid=(left+right)/2;
    build(pos*2,left,mid);
    build(pos*2+1,mid+1,right);
}

void spread_down(int pos){
    t[pos*2].tag=t[pos].tag;
    t[pos*2+1].tag=t[pos].tag;
    t[pos*2].val+=(t[pos*2].r-t[pos*2+1].l+1)*t[pos].tag;
    t[pos*2+1].val+=(t[pos*2+1].r-t[pos*2+1].l+1)*t[pos].tag;
    t[pos].tag=0;
} 

void modify(int pos,int left,int right,int delta){
    if(t[pos].l>=left && t[pos].r<=right){
        t[pos].val+=delta*(t[pos].r-t[pos].l+1);
        t[pos].tag+=delta;
        return;
    }
    int mid=(t[pos].l+t[pos].r)/2;
    if(left<=mid)   modify(pos*2,left,right,delta);
    if(right>mid)   modify(pos*2+1,left,right,delta);
    t[pos].val=t[pos*2].val+t[pos*2+1].val;
    return;
} 

int query(int pos,int left,int right){
    long long ans=0;
    if(t[pos].l>=left&&t[pos].r<=right)
        return t[pos].val;
    int mid=(t[pos].l+t[pos].r)/2;
    if(left<=mid)
        ans+=query(pos*2,left,right);
    if(right>mid)
        ans+=query(pos*2+1,left,right);
    return ans;
}

signed main(){
    //ios::sync_with_stdio(0);
    n=read();
    m=read();
    while(m--){
        int op=read();
        if(op==1){
            int l=read();
            int r=read();
            int d=read();
            modify(1,l,r,d);
        }
        if(op==2){
            int l=read();
            int r=read();
            cout<<query(1,l,r)<<endl;
        }
    }
    return 0;
}

by Yang818 @ 2023-10-20 20:57:55

@半只蒟蒻 我define int longlong了


by Yang818 @ 2023-10-20 20:58:10

@半只蒟蒻 okok谢谢


上一页 |