题目：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 %d ",i); fl=1;} } if(!fl)printf("0 "); 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 %d ",i); fl=1;} } if(!fl)printf("0 "); return 0; }
还有一种二分差分数组的做法，其实很暴力；
不是开两个差分数组每次 memcpy ，而是只开一个记录减少量和原数组比较，会快一点。
代码如下：
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; int const maxn=1e6+5; int n,m,s[maxn],t[maxn],c[maxn],r[maxn],d[maxn]; bool ck(int mid) { memset(c,0,sizeof c); for(int i=1;i<=mid;i++)c[s[i]]+=r[i],c[t[i]+1]-=r[i]; bool fl=0; int tmp=0; for(int i=1;i<=n;i++) { tmp+=c[i]; if(d[i]-tmp<0){fl=1; break;} } return fl; } int main() { scanf("%d%d",&n,&m); for(int i=1,x,pre=0;i<=n;i++)scanf("%d",&d[i]); for(int i=1;i<=m;i++)scanf("%d%d%d",&r[i],&s[i],&t[i]); int l=1,r=m,ans=-1; while(l<=r) { int mid=((l+r)>>1); if(ck(mid))ans=mid,r=mid-1; else l=mid+1; } if(ans==-1)printf("0 "); else printf("-1 %d ",ans); return 0; }