NOIP2012 借教室线段树

一时失言乱红尘 2023-06-04 08:00 19阅读 0赞

[**题目链接**][Link 1]

**看这道题的时候，题目中的借教室我们可以看作是区间修改，如果有一天不符合的话都不行，第一反应就是线段树，维护最小值，查询的时候看是否满足要求，满足的话就区间修改。以此类推，直到出现不满足的情况。**

**但是由于常数问题还是要O2优化才能过，不然只有95分。**

**代码如下：**

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include<cstdio>
    using namespace std;
    const int maxn=1e6+7;
    struct node{
        int l,r,lazy;
        int mi;
    }tree[maxn*4];
    int n,m;
    int val[maxn];
    int d,s,t;
    int ask;
    int re;
    int no;
    bool flag;
    int min(int x,int y){
        return x<y?x:y;
    }
    void build(int now,int l,int r){
        tree[now].l=l,tree[now].r=r;
        if(l==r){
            tree[now].mi=val[l];
            return;
        }
        int mid=(l+r)>>1;
        build(now<<1,l,mid);
        build(now<<1|1,mid+1,r);
        tree[now].mi=min(tree[now<<1].mi,tree[now<<1|1].mi);
    }
    void pushdown(int now){
        if(tree[now].lazy){
            tree[now<<1].mi+=tree[now].lazy;
            tree[now<<1|1].mi+=tree[now].lazy;
            tree[now<<1].lazy+=tree[now].lazy;
            tree[now<<1|1].lazy+=tree[now].lazy;
            tree[now].lazy=0;
        }
    }
    void update(int now,int l,int r,int v){
        if(tree[now].l>=l&&tree[now].r<=r){
            tree[now].lazy+=v;
            tree[now].mi+=v;
            return;
        }
        pushdown(now);
        int mid=(tree[now].l+tree[now].r)>>1;
        if(l<=mid) update(now<<1,l,r,v);
        if(r>mid) update(now<<1|1,l,r,v);
        tree[now].mi=min(tree[now<<1].mi,tree[now<<1|1].mi);
    }
    int query(int now,int l,int r){
        if(tree[now].l>=l&&tree[now].r<=r) return tree[now].mi;
        pushdown(now);
        int mid=(tree[now].l+tree[now].r)>>1;
        int ans=0x3f3f3f3f;
        if(l<=mid) ans=min(ans,query(now<<1,l,r));
        if(r>mid) ans=min(ans,query(now<<1|1,l,r));
        return ans;
    }
    int main(){
        scanf("%d%d",&n,&m);
        for(register int i=1;i<=n;i++) scanf("%d",&val[i]);
        build(1,1,n);
        for(register int i=1;i<=m;i++){
            scanf("%d%d%d",&d,&s,&t);
            ask=d;
            re=query(1,s,t);
            if(ask>re){
                no=i;
                flag=true;
                break;
            }
            else update(1,s,t,-d);
        }
        if(flag) printf("-1\n%d",no);
        else printf("0\n");
        return 0;
    }

转载于:https://www.cnblogs.com/LJB666/p/11523369.html

[Link 1]: https://www.luogu.com.cn/problem/P1083
[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20230601/623de2e9c74e4d4da98f2f48c425f9e0.png