题目：https://www.luogu.org/problemnew/show/P1083
当初不会线段树的时候做这道题...对差分什么不太熟练，一直没A，放在那儿不管...
现在去看，线段树就直接秒了；
不过要注意一下基本的细节囧...
但本题 n 的范围比较微妙，正常线段树会 T 一个点(不过运气好也能过)；
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; int const maxn=1e6+5,maxm=2e7+5; int n,m,a[maxn],mn[maxm],ls[maxm],rs[maxm],cnt=1,lzy[maxm];//cnt=1!! bool fl=0; void pushup(int x){mn[x]=min(mn[ls[x]],mn[rs[x]]);} void pushdown(int x) { if(!lzy[x])return; lzy[ls[x]]+=lzy[x]; lzy[rs[x]]+=lzy[x]; mn[ls[x]]+=lzy[x]; mn[rs[x]]+=lzy[x]; lzy[x]=0; } void build(int x,int l,int r) { if(l==r){mn[x]=a[l]; return;} int mid=((l+r)>>1); ls[x]=++cnt; build(ls[x],l,mid); rs[x]=++cnt,build(rs[x],mid+1,r); pushup(x); } void update(int x,int l,int r,int L,int R,int val) { if(l>=L&&r<=R){mn[x]+=val; lzy[x]+=val; return;} pushdown(x); int mid=((l+r)>>1); if(mid>=L)update(ls[x],l,mid,L,R,val); if(mid<R)update(rs[x],mid+1,r,L,R,val); pushup(x); } int main() { scanf("%d%d",&n,&m); for(int i=1;i<=n;i++)scanf("%d",&a[i]); build(1,1,n); for(int i=1,s,t,r;i<=m;i++) { scanf("%d%d%d",&r,&s,&t); if(fl)continue; update(1,1,n,s,t,-r); if(mn[1]<0){printf("-1\n%d\n",i); fl=1;} } if(!fl)printf("0\n"); return 0; }
所以要加个标记永久化。
代码如下：
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; int const maxn=1e6+5,maxm=2e7+5; int n,m,a[maxn],mn[maxm],ls[maxm],rs[maxm],cnt=1,lzy[maxm];//cnt=1!! bool fl=0; void pushup(int x){mn[x]=min(mn[ls[x]]+lzy[ls[x]],mn[rs[x]]+lzy[rs[x]]);}//+! void build(int x,int l,int r) { if(l==r){mn[x]=a[l]; return;} int mid=((l+r)>>1); ls[x]=++cnt; build(ls[x],l,mid); rs[x]=++cnt,build(rs[x],mid+1,r); // pushup(x); mn[x]=min(mn[ls[x]],mn[rs[x]]);// } void update(int x,int l,int r,int L,int R,int val) { if(l==L&&r==R){lzy[x]+=val; return;} int mid=((l+r)>>1); if(mid<L)update(rs[x],mid+1,r,L,R,val); else if(mid>=R)update(ls[x],l,mid,L,R,val); else update(ls[x],l,mid,L,mid,val),update(rs[x],mid+1,r,mid+1,R,val); pushup(x); } int main() { scanf("%d%d",&n,&m); for(int i=1;i<=n;i++)scanf("%d",&a[i]); build(1,1,n); for(int i=1,s,t,r;i<=m;i++) { scanf("%d%d%d",&r,&s,&t); if(fl)continue; update(1,1,n,s,t,-r); if(mn[1]-lzy[1]<0){printf("-1\n%d\n",i); fl=1;} } if(!fl)printf("0\n"); return 0; }
洛谷 P1083 [ NOIP 2012 ] 借教室 —— 线段树
原文：https://www.cnblogs.com/Zinn/p/9419433.html
