luoguP1083 借教室(题解)(我用的线段树)

luoguP1083 借教室 题目

#include<cstdio>

#include<iostream>

#include<cmath>

#include<string>

#include<string>

#include<algorithm>

#define rg register

#define N 1000050

#define lc now<<1

#define rc (now<<1)+1

using namespace std;

int n,m;

bool flag;

int a[N];

struct tree{

    int l,r,minn,lazy;

}ljl[N<<];

inline int read()

{

    int s=,m=;char ch=getchar();

    while(ch!='-'&&(ch<''||ch>''))ch=getchar();

    if(ch=='-')m=-,ch=getchar();

    while(ch>=''&&ch<='')s=(s<<)+(s<<)+ch-'',ch=getchar();

    return s*m;

}

void build(int now,int ll,int rr)

{

    if(ll==rr)

        {

            ljl[now].l=ljl[now].r=ll;

            ljl[now].minn=a[ll];

        }

    else

        {

            int mid=(ll+rr)>>;

            build(lc,ll,mid);

            build(rc,mid+,rr);

            ljl[now].l=ll;ljl[now].r=rr;

            ljl[now].minn=min(ljl[lc].minn,ljl[rc].minn);

        }

}

void push_down(int now)

{

    if(ljl[now].lazy!=)

        {

            ljl[lc].lazy+=ljl[now].lazy;

            ljl[rc].lazy+=ljl[now].lazy;

            ljl[lc].minn-=ljl[now].lazy;

            ljl[rc].minn-=ljl[now].lazy;

            ljl[now].lazy=;

        }

}

void xiugai(int now,int ll,int rr,int d)

{

    push_down(now);

    if(ljl[now].l==ll&&ljl[now].r==rr)

        {

            ljl[now].lazy+=d;

            ljl[now].minn-=d;

            //            if(ljl[now].minn<0)flag=1;

        }

    else

        {

            int mid=(ljl[now].l+ljl[now].r)/;

            if(rr<=mid)xiugai(*now,ll,rr,d);

            if(ll>mid)xiugai(*now+,ll,rr,d);

            if(ll<=mid&&rr>mid)

                {

                    xiugai(*now,ll,mid,d);

                    xiugai(*now+,mid+,rr,d);

                }

            ljl[now].minn=min(ljl[lc].minn,ljl[rc].minn);

        }

}

int main()

{

    n=read();m=read();

    for(rg int i=;i<=n;++i)a[i]=read();

    build(,,n);

    for(rg int i=;i<=m;++i)

        {

            rg int num=read(),st=read(),et=read();

            xiugai(,st,et,num);

            if(ljl[].minn<)

                {

                    printf("-1\n%d\n",i);

                    exit();

                }

        }

    puts("");

    return ;

}