刚学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 wxwoo @ 2019-06-01 15:03:15

这题不应该分块艹过去吗


by 言和YanHe @ 2019-06-01 15:04:47

@wxwoo 艹过去?!


by wxwoo @ 2019-06-01 15:06:23

@HFOI菠萝 分块不就是暴力吗,暴力不就是艹过去吗


by 小元勋 @ 2019-06-01 15:06:27

@wxwoo 不会分块


by 小元勋 @ 2019-06-01 15:09:52

过了,考了个月考考傻了。 搞忘开4倍了。。。


by WCF_ @ 2019-06-01 15:23:12

这个不是分块吗?


by Juan_feng @ 2019-06-01 15:25:09

@何元勋 显然复杂度是错误的啊


by Juan_feng @ 2019-06-01 15:27:33

@何元勋 您的query函数可能遍历整颗树,而且相当好卡。

说句闲话, 要是区间加区间rank都能log做了那分块就可以退出历史舞台了


by 分块 @ 2019-06-01 15:34:21

@wxwoo 暴力是相对而言吧。

对于本题而言, 我就是正解啦, 暴力什么的, 才不是呢(〃'▽'〃)


by 小元勋 @ 2019-06-01 15:43:34

@Juan_feng 那可能是数据水吧


| 下一页