题意:给定序列,支持区间减少操作,当序列中有负数时停止,输出次数。
#include<bits/stdc++.h>
using namespace std;
int t[4000010];
int N,n,m;
void build(int n)
{
for(N=1;N<=n+1;N<<=1);
memset(t,0,sizeof(int)*(N+N));
for(int i=N+1;i<=N+n;i++)cin>>t[i];
int A;
for(int i=N-1;i>=1;i--)
{
A=min(t[i+i],t[i+i+1]);
t[i+i]-=A;t[i+i+1]-=A;
t[i]+=A;
}
}
int ask(int l,int r)
{
int lmin=0,rmin=0,ans=0;
for(l=l+N,r=r+N;l^r^1;l>>=1,r>>=1)
{
lmin+=t[l];rmin+=t[r];
if(~l&1)lmin=min(lmin,t[l^1]);
if(r&1)rmin=min(rmin,t[r^1]);
}
ans=min(lmin,rmin);
//for(l>>=1;l>=1;l>>=1)ans+=t[l];
while(l>1)ans+=t[l>>=1];
return ans;
}
void change(int l,int r,int x)
{
int A;
for(l=l+N-1,r=r+N+1;l^r^1;l>>=1,r>>=1)
{
if(~l&1)t[l^1]+=x;
if(r&1)t[r^1]+=x;
A=min(t[l],t[l^1]);t[l]-=A;t[l^1]-=A;t[l>>1]+=A;
A=min(t[r],t[r^1]);t[r]-=A;t[r^1]-=A;t[r>>1]+=A;
}
for(;l>1;l>>=1)
{
A=min(t[l],t[l^1]);
t[l]-=A;t[l^1]-=A;
t[l>>1]+=A;
}
}
int main()
{
bool flag=0;
scanf("%d%d",&n,&m);
build(n);
for(int i=1;i<=m;i++)
{
int d,s,e;
cin>>d>>s>>e;
change(s,e,-d);
if(ask(1,n)<0){cout<<"-1"<<endl<<i<<endl;return 0;}
}
cout<<"0"<<endl;
return 0;
}