---

题目描述

某次列车经C个城市，城市编号依次为1到C，列车上共有S个座位，铁路局规定售出的车票只能是坐票，即车上所有的旅客都有座。售票系统是由计算机执行的，每一个售票申请包含三个参数，分别用O,D,N表示，O为起始，D为目的地站，N为车票张数。售票系统对该售票申请作出受理和不受理的决定，只有在从O到D的区段内列车上都有N个和N个以上的空座位时该售票申请才被受理。 请你写一个程序，实现这个自动售票系统。

---

输入格式

输入第一行包含三个用空格隔开的整数C,S和R，其中1 <= C <= 60000,1 <= S <= 60000,1 <= R <= 60000,C为城市个数，S为列车上的座位数，R为所有售票申请总数。 接下来的R行每行为一个售票申请，用三个空格隔开的整数O,D和N表示，O为起始站，D为目的站，N为车票数，其中1<=C<=D,1<=O<=C,所有的售票申请按申请的时间从早到晚给出。

---

输出格式

输出共有R行，每行输出一个”YES”或”NO”，表示当前的售票申请被受理或不受理

---

样例数据

样例输入

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

样例输出

YES YES NO NO

---

题目分析

线段树区间修改区间查询 维护车上剩余空位的最小值 lazy表示坐上车的人数（懒标记） seat表示空位数

---

源代码

#include<algorithm> #include<iostream> #include<iomanip> #include<cstring> #include<cstdlib> #include<vector> #include<cstdio> #include<cmath> #include<queue> using namespace std; inline const int Get_Int() { int num=0,bj=1; char x=getchar(); while(x<'0'||x>'9') { if(x=='-')bj=-1; x=getchar(); } while(x>='0'&&x<='9') { num=num*10+x-'0'; x=getchar(); } return num*bj; } const int maxn=60000; struct Tree { //修改区间 查询区间（+懒标记） int left,right,lazy,seat; //seat表示空位数 lazy表示在父亲结点累积的乘客 }; struct Segment_Tree { //维护空位查询最小值 Tree tree[maxn*4]; int minn; void build(int index,int Left,int Right,int Seat) { tree[index].left=Left; tree[index].right=Right; tree[index].lazy=0; tree[index].seat=Seat; if(Left==Right)return; int mid=(Left+Right)/2; build(2*index,Left,mid,Seat); build(2*index+1,mid+1,Right,Seat); } void push_down(int index) { //标记下传，下传当前lazy（标记为0不下传） if(tree[index].lazy==0)return; tree[2*index].seat-=tree[index].lazy; tree[2*index+1].seat-=tree[index].lazy; tree[2*index].lazy+=tree[index].lazy; tree[2*index+1].lazy+=tree[index].lazy; tree[index].lazy=0; } void push_up(int index) { //标记上传，合并子树信息 tree[index].seat=min(tree[index*2].seat,tree[index*2+1].seat); } void modify(int index,int Left,int Right,int data) { //减去data if(Right<tree[index].left||Left>tree[index].right)return; //不相交 if(Left<=tree[index].left&&Right>=tree[index].right) { //完全包含 tree[index].seat-=data; tree[index].lazy+=data; return; } push_down(index); //标记下传 modify(index*2,Left,Right,data); modify(index*2+1,Left,Right,data); push_up(index); //标记上传 } void init() { minn=0x7fffffff/2; } void Query(int index,int Left,int Right) { if(Right<tree[index].left||Left>tree[index].right)return; //不相交 if(Left<=tree[index].left&&Right>=tree[index].right) { //完全包含 minn=min(minn,tree[index].seat); return; } push_down(index); Query(index*2,Left,Right); Query(index*2+1,Left,Right); push_up(index); } }; Segment_Tree st; int n,Seat,m; int main() { n=Get_Int(); Seat=Get_Int(); m=Get_Int(); st.build(1,1,n,Seat); for(int i=1; i<=m; i++) { int Left=Get_Int(),Right=Get_Int()-1,data=Get_Int(); st.init(); st.Query(1,Left,Right); if(st.minn>=data) { st.modify(1,Left,Right,data); puts("YES"); } else puts("NO"); } return 0; }

---