题目：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+,maxm=2e7+;
int n,m,a[maxn],mn[maxm],ls[maxm],rs[maxm],cnt=,lzy[maxm];//cnt=1!!
bool fl=;
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]=;
}
void build(int x,int l,int r)
{
if(l==r){mn[x]=a[l]; return;}
int mid=((l+r)>>);
ls[x]=++cnt; build(ls[x],l,mid);
rs[x]=++cnt,build(rs[x],mid+,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)>>);
if(mid>=L)update(ls[x],l,mid,L,R,val);
if(mid<R)update(rs[x],mid+,r,L,R,val);
pushup(x);
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=;i<=n;i++)scanf("%d",&a[i]);
build(,,n);
for(int i=,s,t,r;i<=m;i++)
{
scanf("%d%d%d",&r,&s,&t);
if(fl)continue;
update(,,n,s,t,-r);
if(mn[]<){printf("-1\n%d\n",i); fl=;}
}
if(!fl)printf("0\n");
return ;
}
T #13
所以要加个标记永久化。
代码如下：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int const maxn=1e6+,maxm=2e7+;
int n,m,a[maxn],mn[maxm],ls[maxm],rs[maxm],cnt=,lzy[maxm];//cnt=1!!
bool fl=;
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)>>);
ls[x]=++cnt; build(ls[x],l,mid);
rs[x]=++cnt,build(rs[x],mid+,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)>>);
if(mid<L)update(rs[x],mid+,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+,r,mid+,R,val);
pushup(x);
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=;i<=n;i++)scanf("%d",&a[i]);
build(,,n);
for(int i=,s,t,r;i<=m;i++)
{
scanf("%d%d%d",&r,&s,&t);
if(fl)continue;
update(,,n,s,t,-r);
if(mn[]-lzy[]<){printf("-1\n%d\n",i); fl=;}
}
if(!fl)printf("0\n");
return ;
}
还有一种二分差分数组的做法，其实很暴力；
不是开两个差分数组每次 memcpy ，而是只开一个记录减少量和原数组比较，会快一点。
代码如下：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int const maxn=1e6+;
int n,m,s[maxn],t[maxn],c[maxn],r[maxn],d[maxn];
bool ck(int mid)
{
memset(c,,sizeof c);
for(int i=;i<=mid;i++)c[s[i]]+=r[i],c[t[i]+]-=r[i];
bool fl=; int tmp=;
for(int i=;i<=n;i++)
{
tmp+=c[i];
if(d[i]-tmp<){fl=; break;}
}
return fl;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=,x,pre=;i<=n;i++)scanf("%d",&d[i]);
for(int i=;i<=m;i++)scanf("%d%d%d",&r[i],&s[i],&t[i]);
int l=,r=m,ans=-;
while(l<=r)
{
int mid=((l+r)>>);
if(ck(mid))ans=mid,r=mid-;
else l=mid+;
}
if(ans==-)printf("0\n");
else printf("-1\n%d\n",ans);
return ;
}