TZOJ 3315 买火车票(线段树区间最小值)

描述

Byteotian州铁道部决定赶上时代，为此他们引进了城市联网。假设城市联网顺次连接着n 个市从1 到n 编号(起始城市编号为1，终止城市编号为n)。每辆火车有m个座位且在任何两个运送更多的乘客是不允许的。电脑系统将收到连续的预订请求并决定是否满足他们的请求。当火车在请求的路段上有足够的空位时，就通过这个请求，否则不通过。通过请求的一部分是不允许的通过一个请求之后，火车里的空位数目将得到更新。请求应按照收到的顺序依次处理。计算哪些请求可以通过，哪些请求不能通过。

输入

输入数据有多组以EOF结束。每组数据第一行是三个被空格隔开整数n, m 和 r (1<=n<=60 000, 1<=m<=60 000,1<=r<=60 000)。数字分别表示：铁路上的城市个数，火车内的座位数，请求的数目。接下来r 行是连窜的请求。第i+1 行描述第i 个请求。描述包含三个整数k1、k2 和 v (1<=k1<k2<=n, 1<=v<=m)。它们分别表示起点车站的编号，目标车站的编号，座位的需求数。

输出

输出r行，每行一个字符。'Yes'表示可以通过；'No'表示不能通过。每组输出后面有一个空行。

样例输入

4 6 4
1 4 2
1 3 2
2 4 3
1 2 3

样例输出

Yes
Yes
No
No

题意

如上

题解

线段树维护当前区间最少空座位数，初始值全设为M

对于每次询问区间[X，Y），查询区间最小值，若>=p，则更新区间[X，Y)-p

代码

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 
 4 const int N=6e4+5;
 5 int m;
 6 int minn[N<<2],lazy[N<<2];
 7 void PushDown(int rt)
 8 {
 9     if(!lazy[rt])return;
10     lazy[rt<<1]+=lazy[rt];
11     lazy[rt<<1|1]+=lazy[rt];
12     minn[rt<<1]-=lazy[rt];
13     minn[rt<<1|1]-=lazy[rt];
14     lazy[rt]=0;
15 }
16 void Build(int l,int r,int rt)
17 {
18     minn[rt]=m,lazy[rt]=0;
19     if(l==r)
20     {
21         minn[rt]=m;
22         return;
23     }
24     int mid=(l+r)>>1;
25     Build(l,mid,rt<<1);
26     Build(mid+1,r,rt<<1|1);
27     minn[rt]=min(minn[rt<<1],minn[rt<<1|1]);
28 }
29 void Update(int L,int R,int C,int l,int r,int rt)
30 {
31     if(L<=l&&r<=R)
32     {
33         minn[rt]-=C;
34         lazy[rt]+=C;
35         return;
36     }
37     int mid=(l+r)>>1;
38     PushDown(rt);
39     if(L<=mid)Update(L,R,C,l,mid,rt<<1);
40     if(R>mid)Update(L,R,C,mid+1,r,rt<<1|1);
41     minn[rt]=min(minn[rt<<1],minn[rt<<1|1]);
42 }
43 int Query(int L,int R,int l,int r,int rt)
44 {
45     if(L<=l&&r<=R)
46         return minn[rt];
47     int mid=(l+r)>>1,ans=1e9;
48     PushDown(rt);
49     if(L<=mid)ans=min(ans,Query(L,R,l,mid,rt<<1));
50     if(R>mid)ans=min(ans,Query(L,R,mid+1,r,rt<<1|1));
51     minn[rt]=min(minn[rt<<1],minn[rt<<1|1]);
52     return ans;
53 }
54 int main()
55 {
56     int n,r,x,y,p;
57     while(scanf("%d%d%d",&n,&m,&r)!=EOF)
58     {
59         Build(1,n,1);
60         for(int i=0;i<r;i++)
61         {
62             scanf("%d%d%d",&x,&y,&p);
63             int freep=Query(x,y-1,1,n,1);
64             if(freep>=p)Update(x,y-1,p,1,n,1),printf("Yes
");
65             else printf("No
");
66         }
67         printf("
");
68     }
69     return 0;
70 }