Featured image of post 洛谷P1083题解

洛谷P1083题解

题目描述

思路

维护一个线段树,每次输入订单时,做一个区间减法,当某个节点小于0时,直接返回

代码

 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
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
#include<bits/stdc++.h>
#define ____ ((__+___)>>1)
#define length(__,___)  (___-__+1)
#define FOR(i,l,r) for (int i=l;i<=r;i++)
using namespace std;
const int N  = 1000100;
bool flag=0;
int d,s,t,r[N],n,m;
struct Node {
int num,lz,mi;
}
nd[N*4];
inline int read() {register int f=1,k=0;register char c=getchar();while(c!='-'&&(c<'0'||c>'9')) {
c=getchar();
}
if(c=='-') {
f=-1,c=getchar();
}
while(c>='0'&&c<='9') {
k=(k<<3)+(k<<1)+(c^48),c=getchar();
}
return f*k;
}
void pushup(int _) {
nd[_].num=nd[_*2].num+nd[_*2+1].num;
nd[_].mi = min(nd[_*2].mi,nd[_*2+1].mi);
}
void build(int _,int __,int ___) {
if(__ == ___) {
nd[_].num=nd[_].mi=r[__];
return;
} else {
build(_*2,__,____);
build(_*2+1,____+1,___);
pushup(_);
}
}
void pushdown(int _,int __,int ___) {
if(nd[_].lz) {
nd[_*2].lz+=nd[_].lz;
nd[_*2+1].lz+=nd[_].lz;
nd[_*2].num+=nd[_].lz*length(__,____);
nd[_*2+1].num+=nd[_].lz*length(____+1,___);
nd[_*2].mi+=nd[_].lz;
nd[_*2+1].mi+=nd[_].lz;
nd[_].lz=0;
}
}
void update(int _,int __,int ___,int x,int y,int k) {
if(x<=__&&___<=y) {
nd[_].lz-=k;
nd[_].num-=k*length(__,___);
nd[_].mi-=k;
if(nd[_].mi<0) {
flag=1;
}
return;
}
pushdown(_,__,___);
if(x<=____) update(_*2,__,____,x,y,k);
    if(y>____) update(_*2+1,____+1,___,x,y,k);
pushup(_);
}
void DBG(int _,int __,int ___){
if(__==___){
return;
}
cout<<_<<" "<<__<<" "<<___<<" "<<nd[_].lz<<" "<<nd[_].mi<<" "<<nd[_].num<<endl;
DBG(_*2,__,____);
DBG(_*2+1,____+1,___);

}
int main() {
#ifndef ONLINE_JUDGE
freopen("1.in","r",stdin);
#endif
cin>>n>>m;
FOR(i,1,n) {
r[i]=read();
}
build(1,1,n);//printf("i l r lz mi num\n");
// DBG(1,1,n);
// printf("\n");
FOR(i,1,m) {
if(flag==1) {
printf("-1\n%d\n",i-1);
return 0;
}
cin>>d>>s>>t;
update(1,1,n,s,t,d);
// DBG(1,1,n);
// printf("\n");

}
printf("0\n");
return 0;
}

后记

这个题本来老师要求用二分答案来做的,但是线段树本来也是一种二分(吧)。

所念皆星河
Built with Hugo
主题 StackJimmy 设计