cogs 247. 售票系统线段树

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”，表示当前的售票申请被受理或不被受理。

【输入输出样例】

输入:

输出:

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<<2];
LL lazy_tag[maxn<<2];
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]=0;
}
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=1;i<=m;i++)
    {
        int x,y,z;
        scanf("%d%d%d",&x,&y,&z);
        y--;
        if(x>y)
            swap(x,y);//防止卡bug
        Add(1,1,n,x,y,z);
        if(Max(1,1,n,x,y)>S)
        {
            printf("NO
");
            Add(1,1,n,x,y,-z);
        } 
        else
            printf("YES
");
    } 
    return 0;
}