247. 售票系统
★★☆ 输入文件：railway.in 输出文件：railway.out 简单对比
时间限制：1 s 内存限制：128 MB
【问题描述】
某次列车途经C个城市，城市编号依次为1到C，列车上共有S个座位，铁路局规定售出的车票只能是坐票， 即车上所有的旅客都有座。售票系统是由计算机执行的，每一个售票申请包含三个参数，分别用O、D、N表示，O为起始站，D为目的地站，N为车票张数。售票 系统对该售票申请作出受理或不受理的决定，只有在从O到D的区段内列车上都有N个或N个以上的空座位时该售票申请才被受理。请你写一个程序，实现这个自动 售票系统。
【输入格式】
第一行包含三个用空格隔开的整数C、S和R，其中1≤C≤60000， l≤S≤60000，1≤R≤60000。C为城市个数，S为列车上的座位数，R为所有售票申请总数。接下来的R行每行为一个售票申请，用三个由空格隔开的整数O，D和N表示，O为起始站，D 为目的地站，N为车票张数，其中1≤D≤C，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 啊呵呵呵 感觉这一道题好像很简单 又好像很难的样子
所以 。。。这一道题的数据看起来有一点可怕啊
先花n logn的时间建树 60000*20=120 0000 60000个询问 每个logn 也是120 0000
加起来看起来好像没有超时的样子诶~QAQ反正这一道题的标签是线段树 就是说可以先加到线段树中
再查一下区间最大值是否大于总座位数 如果大于就是No 再把区间减去刚才加的值
否则就输出Yes啦 （<<仿佛很简单的样子） 敲一敲试试
然鹅发现事情并不简单 首先要打一个标记 还有一个很坑很坑的点：
我第一次交是33分 那么到底是为什毛？
原因是 这是左闭右开区间
就是说x站到y站 y站是下车的 不算！要在输入后把y--
太尴尬了 本以为能一遍A（太蒟了）
代码如下 （本人萌新 刚学打标记不久QAQ）
#include<bits/stdc++.h>
#define ls (p*2)
#define rs (p*2+1)
#define mid (l+r>>1)
#define lson ls,l,mid
#define rson rs,mid+1,r
#define maxn 60005
#define LL long long
#define INF 0x3f3f3f3f
using namespace std;
int n,S,m;
LL sum[maxn<<];
LL lazy_tag[maxn<<];
void Pushdown(int p,int l,int r)
{
lazy_tag[ls]+=lazy_tag[p];
lazy_tag[rs]+=lazy_tag[p];
sum[ls]+=lazy_tag[p];
sum[rs]+=lazy_tag[p];
lazy_tag[p]=;
}
void Add(int p,int l,int r,int s,int t,int z)
{
if(s>r||t<l)
return ;
if(s<=l && r<=t)
{
sum[p]+=z;//Important 打标记必备
lazy_tag[p]+=z;
return;
}
Pushdown(p,l,r);
Add(lson,s,t,z);
Add(rson,s,t,z);
sum[p]=max(sum[ls],sum[rs]);
return;
}
LL Max(int p,int l,int r,int s,int t)
{
if(s>r||t<l)
return -INF;
if(s<=l&&r<=t)
return sum[p];
Pushdown(p,l,r);
return max(Max(lson,s,t),Max(rson,s,t));
}
int main()
{
freopen("railway.in","r",stdin);
freopen("railway.out","w",stdout);
scanf("%d%d%d",&n,&S,&m);
//build(1,1,n); 这里不需要build 了 一开始值都是0
for(int i=;i<=m;i++)
{
int x,y,z;
scanf("%d%d%d",&x,&y,&z);
y--;
if(x>y)
swap(x,y);//防止卡bug
Add(,,n,x,y,z);
if(Max(,,n,x,y)>S)
{
printf("NO\n");
Add(,,n,x,y,-z);
}
else
printf("YES\n");
}
return ;
}
宏定义一波走天下♪(^∇^*)