首页 > 代码库 > noip2012借教室
noip2012借教室
这道题很明显可以用线段树。
然而区间修改有比它更快，更好写的离线方法，差分数组。
首先这道题需要二分答案，接着用差分数组写check函数。b[i]=a[i]-a[i-1];b[1]=a[1];b为差分数组
我们可以发现一个性质（此处不做证明）对与a[i]的[l,r]区间减少s
相当与在b[l]-s,b[r+1]+s;
check(x)时，先求出b，然后进行修改，在之后判断修改过后的b数组根据a[i]=b[i]+a[i-1]判断a[i]<0即可返回false
#include<cstdio> const int N=1e6+5; int x[N],y[N],z[N],l[N],r[N],sl[N],n,m; bool f(int a) { for(int i=1;i<=n;i++) y[i]=x[i]-x[i-1]; for(int i=1;i<=a;i++) y[l[i]]-=sl[i],y[r[i]+1]+=sl[i]; for(int i=1;i<=n;i++) { z[i]=z[i-1]+y[i]; if(z[i]<0) return 0; } return 1; } int main() { scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) scanf("%d",&x[i]); for(int i=1;i<=m;i++) scanf("%d%d%d",&sl[i],&l[i],&r[i]); int l=0,r=m+1; while(l<r-1) { int mid=(l+r)>>1; if(f(mid)) l=mid; else r=mid; } if(r==m+1) putchar(‘0‘); else printf("-1\n%d",r); return 0; }
noip2012借教室
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。