【题目描述】
现需要处理N天的借教室信息，其中第i天学校有Ri个教室可供租借。共有M份订单，每份订单用三个正整数Dj、Sj、Tj描述，表示某租借者需要从第Sj天到第Tj天租借教室（包括第Sj天和第Tj天），每天需要租借Dj个教室。
借教室的原则是先到先得，如果在分配的过程中遇到一份订单无法满足，则需要停止教室的分配。这里的无法满足指从第Sj天到第Tj天中有至少一天剩余的教室数量不足Dj个。
现询问是否会有订单无法满足。如果有，询问需要通知哪一个申请人修改订单。
【输入描述】
第一行输入两个正整数N、M，表示天数和订单数；
第二行输入N个正整数，表示第i天可用于租借的教室数量；
接下来M行，每行输入三个正整数Dj、Sj、Tj，表示租借的数量、租借开始、结束分别在第几天。
【输出描述】
如果所有订单均可满足，则输出0，否则第一行输出-1，第二行输出需要修改订单的申请人编号。
【样例输入】
4 3
2 5 4 3
2 1 3
3 2 4
4 2 4
【样例输出】
-1
2
【数据范围及提示】
对于100%的数据，1 <= N,M <= 106，0 <= Rj,Dj <= 109，1 <= Sj <= N。
谁说线段树不行，从闹红毛到洋枪队，他们不让线段树上，今天就问线段树威风不！
源代码：#include#include #include using namespace std;int m,n,num(0),number(0),h[1000001];struct tree{ int left,right,lefts,rights,sum,sign;}i[2000200];void x1(int t1,int t2){ int t=++num; i[t].left=t1; i[t].right=t2; if (t1!=t2-1) { i[t].lefts=num+1; x1(t1,(t1+t2)>>1); i[t].rights=num+1; x1((t1+t2)>>1,t2); i[t].sum=min(i[i[t].lefts].sum,i[i[t].rights].sum); } else i[t].sum=h[t1];}void lazy(int t){ i[i[t].lefts].sum-=i[t].sign; i[i[t].rights].sum-=i[t].sign; i[i[t].lefts].sign+=i[t].sign; i[i[t].rights].sign+=i[t].sign; i[t].sign=0;}bool x2(int t,int s,int t1,int t2){ if (t1<=i[t].left&&t2>=i[t].right) { i[t].sum-=s; i[t].sign+=s; if (i[t].sum<0) //就是它，拯救了整个程序！ return false; return true; } if (i[t].sign) lazy(t); bool ans=true; if (t1<(i[t].left+i[t].right)>>1) if (!x2(i[t].lefts,s,t1,t2)||!ans) ans=false; if (t2>(i[t].left+i[t].right)>>1) if (!x2(i[t].rights,s,t1,t2)||!ans) ans=false; i[t].sum=min(i[i[t].lefts].sum,i[i[t].rights].sum); return ans;}int main() //令人惊心动魄的线段树。{ memset(i,0,sizeof(i)); scanf("%d%d",&n,&m); for (int a=1;a<=n;a++) scanf("%d",&h[a]); x1(1,n+1); for (int a=1;a<=m;a++) { int t,t1,t2; scanf("%d%d%d",&t,&t1,&t2); if (!x2(1,t,t1,t2+1)) //结合了查找与判断。 { number=a; break; } } if (number) printf("-1\n%d",number); else printf("0"); return 0;}
要想赶尽洋鬼子呀，还得靠二分+前缀和。
源代码：#includeint m,n,ans(0),h[1000001],i[1000001],X[1000001],L[1000001],R[1000001];void Read(int &t) //读入优化。{ char T=getchar(); while (T<'0'||T>'9') T=getchar(); while (T>='0'&&T<='9') { t=t*10+T-'0'; T=getchar(); }}bool Check() //检验答案。{ int num(0); for (int a=1;a<=n;a++) //前缀和表示单点。 { num+=i[a]; if (num>h[a]) return false; } return true;}int main(){ Read(n); Read(m); for (int a=1;a<=n;a++) Read(h[a]); for (int a=1;a<=m;a++) { Read(X[a]); Read(L[a]); Read(R[a]); } int left=1,right=m,mid=(left+right)>>1; for (int a=1;a<=mid;a++) //二分预处理。 { i[L[a]]+=X[a]; i[R[a]+1]-=X[a]; } while (left<=right) if (!Check()) //有答案就尽量前移。 { ans=mid; right=mid-1; mid=(left+right)>>1; for (int a=mid+1;a<=ans;a++) //注意边界。 { i[L[a]]-=X[a]; //割后。 i[R[a]]+=X[a]; } } else { left=mid+1; mid=(left+right)>>1; for (int a=left;a<=mid;a++) //补后。 { i[L[a]]+=X[a]; i[R[a]]-=X[a]; } } if (!ans) printf("0"); else printf("-1\n%d",ans); return 0;}