[NOIP2012]借教室 题解

题目大意：

　　有一个n个数的数列，m个操作，第i个操作使[l,r]区间建d，问第几个操作使数列中出现负数。

思路：

　　暴力显然过不了，那么就可以优化了，不难想到线段树，显然需要良好的姿势，那么就差分。

　　a[i]表示第i天比第i-1天多了多少房间，于是a的前缀和即为该天的房间数量。而a的维护显然为a[l]+=d,a[r+1]-=d

　　因为求最前的操作，于是我们可以二分答案。但如此常数比较大，又有冗余，可以来个栈一样的东西节省时间。

　　但是有大神想到了O(n+m)的算法。假设m个指令都可满足，天数从前往后判断，再从后往前一个一个删除指令，直到无负数为止。

代码：

　　二分：

 #include<cstdio>

 const int M=;

 int n,m,i,k,h,t,sum,last,a[M],l[M],r[M],d[M],b[M];

 bool can;

 int read()

 {

     int x=;

     char ch=getchar();

     while (ch<'' || ch>'') ch=getchar();

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

     return x;

 }

 int main()

 {

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

     for (i=;i<=n;++i) b[i]=read();

     for (i=;i<=m;++i) d[i]=read(),l[i]=read(),r[i]=read();

     for (h=,t=m;h<t;)

     {

         m=h+t>>;

         if (m>last) for (i=last+;i<=m;++i) a[l[i]]=a[l[i]]+d[i],a[r[i]+]=a[r[i]+]-d[i];

         else if (m<last) for (i=m+;i<=last;++i) a[l[i]]=a[l[i]]-d[i],a[r[i]+]=a[r[i]+]+d[i];

         for (last=m,sum=,i=can=;i<=n;++i)

         {

             sum=sum+a[i];

             if (sum>b[i]) { can=; break; }

         }

         if (can) h=m+; else t=k=m;

     }

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

     else printf("0\n");

     return ;

 }

　　O(n+m):

 #include<cstdio>

 const int M=;

 int n,m,i,x,cnt,a[M],b[M],l[M],r[M],d[M];

 int read()

 {

     int x=; char ch=getchar();

     while (ch<'' || ch>'') ch=getchar();

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

     return x;

 }

 int main()

 {

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

     for (i=;i<=n;++i) a[i]=(b[i]=read())-b[i-];

     for (i=;i<=m;++i) d[i]=read(),a[l[i]=read()]=a[l[i]]-d[i],a[(r[i]=read())+]=a[r[i]+]+d[i];

     for (x=m,i=;i<=n;++i)

         for (cnt=cnt+a[i];cnt<;--m)

             if (l[m]>i) a[l[m]]=a[l[m]]+d[m],a[r[m]+]=a[r[m]+]-d[m];

             else if (r[m]>=i) cnt=cnt+d[m],a[r[m]+]=a[r[m]+]-d[m];

     if (m<x) printf("-1\n%d\n",m+);

     else printf("0\n");

     return ;

 }