P1083 借教室
题面:https://www.luogu.org/problem/P1083
一题简单的线段树(但在这题看来似乎是一种玄学算法)
开一个线段树维护区间最小值和支持区间修改即可
只要整个区间中有<0的就不行,即教室不够了.输出当前的订单号就行.Code:
#include
#include
#include
#include
#include
#include
#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"< 转载于:https://www.cnblogs.com/ukcxrtjr/p/11382433.html
本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！