贴一下线段树AC程序
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=1000000+10;
int n,m;
int a[maxn];
int tree[maxn*4],d[maxn*4];
void buildtree(int k,int x,int y)
{
if(x==y)
{
tree[k]=a[x];
return ;
}
int m=x+(y-x)/2;
buildtree(k*2,x,m);
buildtree(k*2+1,m+1,y);
tree[k]=min(tree[k*2],tree[k*2+1]);
}
void xiugai(int k,int x,int y,int l,int r,int b)
{
if( r<x || l>y )
{
return ;
}
if( x>=l && y<=r )
{
d[k]+=b;
return ;
}
if(d[k])
{
d[k*2]+=d[k];
d[k*2+1]+=d[k];
d[k]=0;
}
int m=x+(y-x)/2;
xiugai(k*2,x,m,l,r,b);
xiugai(k*2+1,m+1,y,l,r,b);
tree[k]=min(tree[k*2]+d[2*k],tree[k*2+1]+d[2*k+1]);
}
void init()
{
}
void readdata()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
buildtree(1,1,n);
int x,y,z;
for(int i=1;i<=m;i++)
{
scanf("%d%d%d",&z,&x,&y);
xiugai(1,1,n,x,y,-z);
if(tree[1]<0)
{
printf("-1\n%d\n",i);
return ;
}
}
printf("0");
}
void work()
{
}
int main()
{
init();
readdata();
work();
return 0;
}