题解 P1083 【借教室】

wrpwrp · 2019-08-11 16:47:42 · 题解

线段树真的很方便啊，个人觉得比差分好想诶？？ 线段树做法： 维护一个区间最小值来判断是否可以安排 每个叶子节点表示第几天的剩余教室 然后订就是区间减法，然后同时判断一下就ok了 注释就不写了吧...数据结构题，我的函数名还是比较明了的q; 代码如下：

#include <cstdio>
using namespace std;

#define MAXN 1000005
#define MAXM 1000005
#define R register
#define GC getchar()
#define PC(a) putchar(a+48)
#define inf 2147483647

struct node {int l,r,minn,tag;}t[MAXM<<2];

template <typename T> inline void read(T &x);
template <typename T> inline void print(T x);
template <typename T> inline T max(T x,T y);
template <typename T> inline T min(T x,T y);

inline int ls(int x);
inline int rs(int x);
inline void down(int x);
inline void build (int L,int R,int x);
inline void change(int num,int ll,int rr,int x,int &ff);

int main()
{
    R int n,m;
    read(n),read(m);
    build(1,n,1);
    R int d,s,t,f;
    for(R int i=1;i<=m;i++)
    {
        read(d),read(s),read(t);
        f=0;
        change(d,s,t,1,f);
        if(f) {printf("-1\n%d\n",i);return 0;}
    }
    print(0);
    return 0;
}

template <typename T>
inline void read(T &x)
{
    char a=GC;int f=1;x=0;
    for(;a>'9'||a<'0';a=GC) if(a=='-') f=-1;
    for(;a>='0'&&a<='9';a=GC) x=(x<<1)+(x<<3)+(a^48);
    x*=f;
}

template <typename T> 
inline void print(T x)
{
    int tot=0,a[20];int f=0;
    if(x<0) putchar(' '),x=-x,f=1;
    if(x==0) {putchar('0');putchar('\n');return;}
    while(x) {a[++tot]=x%10;x/=10;}
    if(f) putchar('-');
    while(tot) PC(a[tot--]);
    putchar('\n');
}

template <typename T> inline T max(T x,T y) {return x>y?x:y;}
template <typename T> inline T min(T x,T y) {return x<y?x:y;}
inline int ls(int x) {return x<<1;}
inline int rs(int x) {return x<<1|1;}

inline void build(int LL,int RR,int x)
{
    t[x].l=LL;t[x].r=RR;t[x].tag=0;t[x].minn=inf;
    if(LL==RR) {read(t[x].minn);return;}
    R int mid=LL+RR;mid>>=1;
    build(LL,mid,ls(x));
    build(mid+1,RR,rs(x));
    t[x].minn=min(t[ls(x)].minn,t[rs(x)].minn);
}

inline void change(int num,int ll,int rr,int x,int &ff)
{
    if(t[x].l>=ll&&t[x].r<=rr) 
    {
        if(t[x].minn<num) {ff=1;return;}
        t[x].minn-=num;
        t[x].tag+=num;
        return;
    }
    if(t[x].tag) down(x);
    int mid=t[x].l+t[x].r;mid>>=1;
    if(ll<=mid)
    change(num,ll,rr,ls(x),ff);
    if(rr>mid)
    change(num,ll,rr,rs(x),ff);
    t[x].minn=min(t[ls(x)].minn,t[rs(x)].minn);
}

inline void down(int x)
{
    t[ls(x)].tag+=t[x].tag;
    t[rs(x)].tag+=t[x].tag;
    t[ls(x)].minn-=t[x].tag;
    t[rs(x)].minn-=t[x].tag;
    t[x].tag=0;
}

线段树，你值得拥有