刚学oi的孩子真的不会线段树

P2801 教主的魔法

小元勋 @ 2019-06-01 15:01:37

RE,求助大佬

#include <bits/stdc++.h>
using namespace std;
#define maxn 1000010
#define maxm 3010
#define mid ((l+r)>>1)
#define lson l,mid,nod<<1
#define rson mid+1,r,nod<<1|1
#define Love long long
int n,m,a[maxn];
Love ans=0,la[maxn],mi[maxn];

inline int read_() {
    int 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<<3)+(x<<1)+c-'0';
        c=getchar();
    }
    return x*f;
}

inline void pushup_(int nod) {
    mi[nod]=min(mi[nod<<1],mi[nod<<1|1]);
}

void build_(int l,int r,int nod) {
    if(l==r) {
        mi[nod]=a[l];
        return;
    }
    build_(lson);
    build_(rson);
    pushup_(nod);
}

inline void xiugai_(int l,int r,int nod,int v) {
    mi[nod]+= (Love) v;
    la[nod]+= (Love) v;       
}

inline void pushdown_(int l,int r,int nod) {
    //if(!la[nod]) return;
    xiugai_(lson,la[nod]);
    xiugai_(rson,la[nod]);
    la[nod]=0;
}

void update_(int l,int r,int nod,int LL,int RR,int v) {
    if(LL<=l&&RR>=r) {
        xiugai_(l,r,nod,v);
        return;
    }
    if(la[nod]) pushdown_(l,r,nod);
    if(LL<=mid) update_(lson,LL,RR,v);
    if(RR>mid) update_(rson,LL,RR,v);
    pushup_(nod);
}

void query_(int l,int r,int nod,int LL,int RR,int v) {
    if(LL<=l&&RR>=r&&mi[nod]>=v) {
        ans+=r-l+1;
        return;
    }
    if(l==r) return ;
    if(la[nod]) pushdown_(l,r,nod);
    if(LL<=mid) query_(lson,LL,RR,v);
    if(RR>mid) query_(rson,LL,RR,v);
}

void readda_() {
    n=read_();m=read_();
    for(int i=1;i<=n;++i) {
        a[i]=read_();
    }
    memset(la,0,sizeof(la));
    memset(mi,0,sizeof(mi));
    build_(1,n,1);
    int x,y,z;
    for(int i=1;i<=m;++i) {
        char c;
        cin>>c;
        x=read_();y=read_();z=read_();
        if(c=='M') {
            update_(1,n,1,x,y,z);
        }
        else {
            ans=0;
            query_(1,n,1,x,y,z);
            printf("%lld\n",ans);
        }
    }
}

int main() {
    freopen("a.txt","r",stdin);
    readda_();
    return 0;
}

by chdy @ 2019-06-24 08:33:17

搞事情啊 直接树套树算了 貌似空间爆了。。


上一页 |