P1083 借教室（标记永久化线段树/二分+前缀和）难度⭐⭐⭐★

P1083 借教室

标记永久化线段树

很典型的区间修改问题，先输入赋值建树（这就是最典型的线段树呀，别忘了），然后修改
这里问的是是否有足够的空教室，所以线段树中 min 代表的是当前区间内最小的剩余教室量。
一般的线段树使用lazytag标记，每次都需要往下修改到根节点，本题中1e6有可能被卡常超时，所以使用标记永久化的线段树，即不用lazytag，改用used表示当前区间所使用的教室数，更新节点的时候用tree[p].minn=min(tree[p].minn,min(tree[ls].minn-tree[ls].used,tree[rs].minn-tree[rs].used));即可
标记永久化的好处是速度会变快，以及便于删除标记。但是这道题没有删除操作。

#include<bits/stdc++.h>
#define ls (p<<1)
#define rs (p<<1|1)
#define mid ((l+r)>>1)
using namespace std;
typedef long long ll;
//线段树维护的是当前区间里最小的剩余教室量
//线段树是从1开始的
const ll N=1e6+7;
struct segment
{
    ll l,r,minn;//当前区间最小剩余教室量
    ll used;//当前区间教室使用量
}tree[N<<2];//线段树要开四倍

ll arr[N],n,m,l,r,d;

inline void build(ll p,ll l,ll r)
{
    tree[p].l=l,tree[p].r=r;
    if(l==r)
    {
        tree[p].minn=arr[l];
        return;
    }
    build(ls,l,mid);
    build(rs,mid+1,r);
    tree[p].minn=min(tree[ls].minn,tree[rs].minn);
}

inline void update(ll p)
{
    tree[p].minn=min(tree[p].minn,min(tree[ls].minn-tree[ls].used,tree[rs].minn-tree[rs].used));
}

#undef mid

inline void change(ll p,ll l,ll r,ll k)
{
    if(tree[p].l==l&&tree[p].r==r)
    {
        tree[p].used+=k;
        return ;
    }
    //if(tree[p].r>=l)
    // change(ls,l,r,k);
    //if(tree[p].l<=r)
    // change(rs,l,r,k);
    ll mid=(tree[p].l+tree[p].r)>>1;
    if(r<=mid)change(ls,l,r,k);
    else if(l>mid)change(rs,l,r,k);
    else change(ls,l,mid,k),change(rs,mid+1,r,k);
    update(p);
}

int main()
{
    scanf("%lld %lld",&n,&m);
    for(int i=1;i<=n;++i)
        scanf("%lld",&arr[i]);
    build(1,1,n);
    for(int i=1;i<=m;++i)
    {
        scanf("%lld%lld%lld",&d,&l,&r);
        change(1,l,r,d);
        if(tree[1].minn-tree[1].used<0)//现有的减去使用过的
        {
            printf("-1\n%d\n",i);
            return 0;
        }
    }
    printf("0\n");
    return 0;
}

二分+前缀和

还没写，明天补上

有任何疑问欢迎评论哦虽然我真的很菜