Part2.3 P1083 借教室 【线段树】

原题链接：P1083 [NOIP2012 提高组] 借教室 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

题意：共 n 天，每天提供 ri 个教室，然后有 m 个查询，需要从 sj 到 tj 每天租借 dj 个教室， 如果无法满足则输出 -1 并且输出第一个不满足的查询编号，全部满足则输出 0

思路：考虑到区间查询和修改，选择用带懒标记的线段树进行维护，节点只需记录最小值和额外标记即可，若区间最小值不满足查询值 d 即可 break ，否则则进行区间更新

评价：线段树板子

 1 #include
 2 using namespace std;
 3 //#define mod 1000000007
 4 typedef long long ll;
 5 ll n,m,a[1000005];
 6 struct node
 7 {
 8     int l,r;
 9     ll mi,add;
10 }tr[4000020];
11 struct qq
12 {
13     ll d;
14     int l,r;
15 }q[1000005];
16 void pushup(int u)
17 {
18     tr[u].mi=min(tr[u<<1].mi,tr[u<<1|1].mi);
19 }
20 void pushdown(int u)
21 {
22     tr[u<<1].mi-=tr[u].add;
23     tr[u<<1].add+=tr[u].add;
24     tr[u<<1|1].mi-=tr[u].add;
25     tr[u<<1|1].add+=tr[u].add;
26     tr[u].add=0;
27 }
28 void build(int u,int l,int r)
29 {
30     tr[u].l=l;
31     tr[u].r=r;
32     tr[u].add=0;
33     if(l==r) {tr[u].mi=a[r];return;}
34     int mid=(tr[u].l+tr[u].r)/2;
35     build(u<<1,l,mid);
36     build(u<<1|1,mid+1,r);
37     pushup(u);
38 }
39 void update(int u,int l,int r,ll c)
40 {
41     if(tr[u].l>=l&&tr[u].r<=r)
42     {
43         tr[u].mi-=c;
44         tr[u].add+=c;
45     }
46     else
47     {
48         pushdown(u);
49         int mid=(tr[u].l+tr[u].r)/2;
50         if(l<=mid) update(u<<1,l,r,c);
51         if(r>mid) update(u<<1|1,l,r,c);
52         pushup(u);
53     }
54 }
55 ll query(int u,int l,int r)
56 {
57     if(tr[u].l>=l&&tr[u].r<=r) return tr[u].mi;
58     pushdown(u);
59     int mid=(tr[u].l+tr[u].r)/2;
60     ll res=0x3f3f3f3f3f3f3f3f;
61     if(l<=mid) res=min(res,query(u<<1,l,r));
62     if(r>mid) res=min(res,query(u<<1|1,l,r));
63     return res;
64 }
65 int main()
66 {
67     bool ok=true;
68     scanf("%lld%lld",&n,&m);
69     for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
70     build(1,1,n);
71     for(int i=1;i<=m;i++) scanf("%lld%d%d",&q[i].d,&q[i].l,&q[i].r);
72     for(int i=1;i<=m;i++)
73     {
74         ll d=q[i].d,l=q[i].l,r=q[i].r;
75         ll cur=query(1,l,r);
76         if(cur<d)
77         {
78             printf("-1\n%d",i);
79             ok=false;
80             break;
81         }
82         else update(1,l,r,d);
83     }
84     if(ok) printf("0");
85     return 0;
86 }