2012NOIP DAY2T1 方法1：线段树 使用线段树来维护一个区间的最小值，每次对于输入的L,R区间进行区间修改，如果最小值<0，则无法成功借教室（加了一大堆玄学优化，终于勉强没T）
#include <cstdio> #include <stdlib.h> using namespace std; const int maxn=1e6+100; struct tree{ int minn; int l,r; int adi; }st[maxn*4]; int a[maxn]; int w; inline int min(int a,int b) { return a < b ? a : b; } void build(int o,int l,int r) { st[o].l=l,st[o].r=r; if(l==r) { st[o].minn=a[l]; return; } int mid=(r+l)>>1; build((o<<1),l,mid); build((o<<1)|1,mid+1,r); st[o].minn=min(st[(o<<1)].minn,st[(o<<1)|1].minn); } inline void push_down(int o) { int add=st[o].adi; st[o].adi=0; st[(o<<1)].adi+=add; st[(o<<1)|1].adi+=add; st[(o<<1)].minn+=add; st[(o<<1)|1].minn+=add; } inline void query(int o,int ql,int qr,int ad) { int l=st[o].l,r=st[o].r; if(l==ql&&r==qr) { st[o].adi+=ad; st[o].minn+=ad; if(st[o].minn<0) { printf("-1\n%d\n",w); exit(0); } return; } if(st[o].adi) push_down(o); int mid=(l+r)>>1; if(qr<=mid) query((o<<1),ql,qr,ad); else if(ql>mid) query((o<<1)|1,ql,qr,ad); else query((o<<1),ql,mid,ad),query((o<<1)|1,mid+1,qr,ad); st[o].minn=min(st[(o<<1)].minn,st[(o<<1)|1].minn); } inline int read() { int data=0,w=1; char ch=0; while(ch!='-' && (ch<'0' || ch>'9')) ch=getchar(); if(ch=='-') w=-1,ch=getchar(); while(ch>='0' && ch<='9') data=data*10+ch-'0',ch=getchar(); return data*w; } int main() { int n,m; n=read(); m=read(); for (int i = 1; i <= n; i++) { char c = getchar(); while(c < '0' || c > '9') c = getchar(); while(c >= '0' && c <= '9') { a[i] *= 10; a[i] += c - '0'; c = getchar(); } } build(1,1,n); for(int i=1;i<=m;i++) { int x,y,t; t=read(); x=read(); y=read(); w=i; query(1,x,y,-t); } printf("0"); return 0; }方法2：二分+差分 二分能够成功的方案数，用差分进行区修改，暴力判断有没有超出限制的，时间复杂度O（nlogn） 其实跟线段树的复杂度相同，只是常数比较小，在数据爆炸的题里会快不少！
#include <cstdio> #include <stdlib.h> #include <iostream> #include <cstring> using namespace std; const int maxn=1001000; struct tree{ int l,r,t; }a[maxn]; int d[maxn]; int b[maxn]; inline int read() { int data=0,w=1; char ch=0; while(ch!='-' && (ch<'0' || ch>'9')) ch=getchar(); if(ch=='-') w=-1,ch=getchar(); while(ch>='0' && ch<='9') data=data*10+ch-'0',ch=getchar(); return data*w; } int n,m; inline bool check(int mid) { memset(b,0,sizeof(b)); for(int i=1;i<=mid;i++) b[a[i].l]+=a[i].t,b[a[i].r+1]-=a[i].t; int s=0; for(int i=1;i<=n;i++) { s+=b[i]; if(s>d[i]) return 0; } return 1; } int main() { n=read(); m=read(); for(int i=1;i<=n;i++) d[i]=read(); for(int i=1;i<=m;i++) a[i].t=read(),a[i].l=read(),a[i].r=read(); int l=1; int r=m; int ans=0; while(l<=r) { int mid=(l+r)/2; if(!check(mid)) ans=mid,r=mid-1; else l=mid+1; } if(!ans) printf("0"); else printf("-1\n%d",ans); return 0; }