题面:https://www.luogu.org/problem/P1083
一题简单的线段树(但在这题看来似乎是一种玄学算法)
开一个线段树维护区间最小值和支持区间修改即可
只要整个区间中有<0的就不行,即教室不够了.输出当前的订单号就行.
Code:
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
#include<cmath>
#include <iostream>
#define MAXN 10000010
#define inf 0x3f3f3f3f
using namespace std;
struct node{
int l,r;
int add;
int mn;
}tree[MAXN<<2];
void pushup(int index){
tree[index].mn = min(tree[index<<1].mn,tree[index<<1|1].mn);
}
void pushdown(int index){
if(tree[index].add){
tree[index<<1].mn += tree[index].add;
tree[index<<1|1].mn += tree[index].add;
tree[index<<1].add += tree[index].add;
tree[index<<1|1].add += tree[index].add;
tree[index].add = 0;
}
}
void build(int l,int r,int index){
tree[index].l = l;
tree[index].r = r;
tree[index].add = 0;
if(l == r){
scanf("%d",&tree[index].mn);
return ;
}
int mid = (l+r)>>1;
build(l,mid,index<<1);
build(mid+1,r,index<<1|1);
pushup(index);
}
void updata(int l,int r,int index,int val){
if(l <= tree[index].l && r >= tree[index].r){
tree[index].mn += val;
tree[index].add += val;
return ;
}
pushdown(index);
int mid = (tree[index].l+tree[index].r)>>1;
if(l <= mid){
updata(l,r,index<<1,val);
}
if(r > mid){
updata(l,r,index<<1|1,val);
}
pushup(index);
}
int main()
{
int n,m,x,y,z;
scanf("%d%d",&n,&m);
build(1,n,1);
for(int i=1;i<=m;i++){
scanf("%d%d%d",&z,&x,&y);
updata(x,y,1,-z);
if(tree[1].mn<0){
cout<<"-1"<<endl<<i<<endl;
return 0;
}
}
cout<<"0"<<endl;
return 0;
}