「题解」Luogu 1083「借教室」

分析

抽象出模型就是一个区间减的线段树,查询可以直接查询根节点。

建树不要把建左右子树建成根,,,

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include<cstdio>
#include<cctype>
const int MAXN = 10000000 + 6;
int read(){
int op = 1,ans = 0;char s = getchar();
while(!isdigit(s)){if(s == '-'){op = -1;}s = getchar();}
while(isdigit(s)){ans = ans * 10 + s - '0';s = getchar();}
return ans * op;
}
struct SegmentTree{
int l,r,add,MIN;
};SegmentTree T[MAXN * 4];
inline int L(int x){return x << 1;}
inline int R(int x){return x << 1 | 1;}
inline int mid(int l,int r){return (l + r) >> 1;}
inline int min(int a,int b){return a < b ? a : b;}
inline void maintain(int p){T[p].MIN = min(T[L(p)].MIN,T[R(p)].MIN);}
void build(int p,int l,int r){
T[p].l = l,T[p].r = r;
if(l == r){
T[p].MIN = read();
return;
}
build(L(p),l,mid(l,r));
build(R(p),mid(l,r) + 1,r);
maintain(p);
}
void spread(int p){
if(T[p].add){
T[L(p)].MIN += T[p].add;
T[R(p)].MIN += T[p].add;
T[L(p)].add += T[p].add;
T[R(p)].add += T[p].add;
T[p].add = 0;
}
}
void change(int p,int l,int r,int k){
if(l <= T[p].l && T[p].r <= r){
T[p].MIN += k;
T[p].add += k;
return;
}
spread(p);
if(l <= mid(T[p].l,T[p].r)) change(L(p),l,r,k);
if(r > mid(T[p].l,T[p].r)) change(R(p),l,r,k);
maintain(p);
}
int main(){
//freopen("in.txt","r",stdin);
int n,m,d,s,t;n = read();m = read();
register int i;
build(1,1,n);
for(i = 1;i <= m;i++){
d = read();s = read();t = read();
change(1,s,t,-d);
if(T[1].MIN < 0){printf("-1\n%d",i);return 0;}
}
printf("0");

return 0;
}
分享到