售票系统(线段树 (star ))
- 某次列车途经 (C) 个城市,城市编号依次为 (1) 到 (C),列车上共有 (S) 个座位,铁路局规定售出的车票只能是坐票, 即车上所有的旅客都有座。售票系统是由计算机执行的,每一个售票申请包含三个参数,分别用 (O,D,N) 表示,(O) 为起始站,(D) 为目的地站,(N) 为车票张数。售票 系统对该售票申请作出受理或不受理的决定,只有在从 (O) 到 (D) 的区段内列车上都有 (N) 个或 (N) 个以上的空座位时该售票申请才被受理。
- 请你写一个程序,实现这个自动售票系统。
Input
- 第一行包含三个用空格隔开的整数 (C,S) 和 (R),其中 (1≤C≤60000, l≤S≤60000,1≤R≤60000)。(C) 为城市个数,(S) 为列车上的座位数,(R) 为所有售票申请总数。
- 接下来的 (R) 行每行为一个售票申请,用三个由空格隔开的整数 (O,D) 和 (N) 表示,(O) 为起始站,(D) 为目的地站,(N) 为车票张数,其中 (1≤O<D≤C),所有的售票申请按申请的时间从早到晚给出。
Output
- 输出共有 (R) 行,每行输出一个 (YES) 或 (NO),表示当前的售票申请被受理或不被受理。
Sample Input
4 6 4
1 4 2
1 3 2
2 4 3
1 2 3
Sample Output
YES
YES
NO
NO
Hint
- 来源:(cogs247)
分析
- 此题是一道典型的区间修改,区间查询的例子,所以用线段树解决。
- 转移买票时从 (s) 买到 (t) 实际上只在 ([s,t)) 占用了座位,第 (t) 站时并未占用座位,所以在修改和查询的时候把 (t) 减一。
Code
#include <bits/stdc++.h>
const int maxn=6e4+5;
int a[maxn<<2],lazy[maxn<<2];
int le,ri;
void Updata(int rt){
a[rt<<1]+=lazy[rt];
a[rt<<1|1]+=lazy[rt];
lazy[rt<<1]+=lazy[rt];
lazy[rt<<1|1]+=lazy[rt];
lazy[rt]=0;
}
int Query(int rt,int l,int r,int s,int t){
if(s<=l && t>=r) return a[rt];
Updata(rt);
int mid=(l+r)/2;
if(t<=mid) return Query(rt<<1,l,mid,s,t);
if(s>mid) return Query(rt<<1|1,mid+1,r,s,t);
return std::max(Query(rt<<1,l,mid,s,t),Query(rt<<1|1,mid+1,r,s,t));
}
void Insert(int x,int rt,int l,int r,int s,int t){
if(s<=l && t>=r){
a[rt]+=x;
lazy[rt]+=x;
return;
}//在Insert前已经查询过了s~t,lazy标记已更新,所以此时不须Updata
int mid=(l+r)/2;
if(s<=mid) Insert(x,rt<<1,l,mid,s,t);
if(t>mid) Insert(x,rt<<1|1,mid+1,r,s,t);
a[rt]=std::max(a[rt<<1],a[rt<<1|1]);
}
void Solve(){
int n,S,R;scanf("%d%d%d",&n,&S,&R);
for(int i=1;i<=R;i++){
int s,t,x;scanf("%d%d%d",&s,&t,&x);
t--;//买s到t的票,t站时已下车,并未占位置
int left=Query(1,1,n-1,s,t);//插询s~t卖出做多的站
if(left+x<=S){//已卖的+现要买的不超过了S才能卖
printf("YES
");
Insert(x,1,1,n-1,s,t);
}
else
printf("NO
");
}
}
int main(){
Solve();
return 0;
}