洛谷 P1038 [NOIP2012] 借教室

学校大门

简析

很显然这是一道差分+二分答案的题但我偏不这么写线段树的裸题。裸到什么程度呢？你需要实现一颗支持如下操作的线段树：

• 递归建树，自底向上（不然你要执行n次add操作吗？慢死你）

• 区间修改（这个不用说，把预约了的教室数量减掉）

• 查询区间最小值（一旦这个最小值小于0，则判断不满足题意）

值得注意的是，由于是查询区间最小值，所以在初始化时应当将线段树节点所存的值设为无穷大，并很显然地将 \(pushup\) 操作改为取左右子树的较小值即可。同时，在每次 \(pushup\) 操作完毕之后，检查一下当前节点值是否小于 \(0\)，使用一个全局 \(bool\) 变量 \(flag\) 记录是否满足条件，如果不满足，将 \(flag\) 归零并及时结束所有操作直接按题意输出当前的预约编号即可（对于单组数据节省时间的办法）。

由于线段树常数比较大，实测第十三个测试点会被卡，加个快读就能过了，可以说是非常水蓝的题了。

AC代码

#include<iostream>
#include<cstdio>
#include<cctype>
using namespace std;
const int inf = (1<<31)-1;
int read(){
    int re = 0,ch = getchar();
    while(!isdigit(ch)) ch = getchar();
    while(isdigit(ch)) re = (re<<1) + (re<<3) + ch - ‘0‘,ch = getchar();
    return re;
}
struct node{
    int l,r,sum,add;
    #define l(x) t[x].l
    #define r(x) t[x].r
    #define sum(x) t[x].sum
    #define add(x) t[x].add
    #define mid(x) (t[x].l + t[x].r >> 1)
}t[4000006];
bool flag = 1;
int num[1000006];
void check(int x){
    if(sum(x) < 0) flag = 0;
    //cout << "Now node is" << l(x) << ‘ ‘ << r(x) << endl << "Val is" << sum(x) << endl << endl; 
}
void pushup(int x){
    sum(x) = min(sum(x<<1),sum(x<<1|1));
}
void pushdown(int x){
    if(add(x)){
        sum(x<<1) -= add(x);
        sum(x<<1|1) -= add(x);
        add(x<<1) += add(x);
        add(x<<1|1) += add(x);
        add(x) = 0;
    }
}
void build(int x,int l,int r){
    l(x) = l;
    r(x) = r;
    add(x) = 0;
    sum(x) = inf;
    if(l == r){
        sum(x) = num[l];
        return;
    }
    build(x<<1,l,mid(x));
    build(x<<1|1,mid(x) + 1,r);
    pushup(x);
    //cout << "Now node is" << l(x) << ‘ ‘ << r(x) << endl << "Val is" << sum(x) << endl << endl; 
} 
void addnum(int x,int l,int r,int v){
    if(!flag) return;
    if(l <= l(x) && r >= r(x)){
        add(x) += v;
        sum(x) -= v;
        return;
    }
    pushdown(x);
    if(l <= mid(x)) addnum(x<<1,l,r,v);
    if(r > mid(x)) addnum(x<<1|1,l,r,v);
    pushup(x);
    check(x);
}
int n,m;
int main(){
    n = read(),m = read();
    for(int i = 1;i <= n;i++) num[i] = read();
    build(1,1,n);
    for(int i = 1;i <= m;i++){
        int d = read(),s = read(),t = read();
        flag = 1;
        addnum(1,s,t,d);
        if(!flag){
            printf("-1\n%d",i);
            return 0; 
        }
    }
    printf("0\n");
    return 0;
}

洛谷 P1038 [NOIP2012] 借教室

原文：https://www.cnblogs.com/mysterious-garden/p/9834009.html