1291 火車線路

某列火車行使在C個城市之間(出發的城市編號為1，結束達到的城市的編號為C)，假設該列火車有S個座位，現在有R筆預訂票的業務。現在想對這R筆業務進行處理，看哪些預定能滿足，哪些不能滿足。

一筆預定由O、D、N三個整數組成，表示從起點站O到目標站D需要預定N個座位。一筆預定能滿足是指該筆業務在行程範圍內有能滿足的空座位，否則就不能滿足。一筆業務不能拆分，也就是起點和終點站不能更改，預定的座位數目也不能更改。所有的預定需求按給出先後順序進行處理。

請你編寫程式，看那些預定業務能滿足，那些不能滿足。

       輸入文件中的第一行為三個整數C、S、R，(1<=c<=60 000, 1<=s<=60 000, 1<=r<=60 000)他們之間用空隔分開。接下來的R行每行為三個整數O、D、N，(1<=o<d<=c, 1<=n<=s)，分別表示每一筆預定業務。

       對第I筆業務，如果能滿足，則在輸出文件中的第I行輸出“T”，否則輸出“N”

4 6 4

1 4 2

1 3 2

2 4 3

1 2 3

T

T

N

N‘

’mmzz題目有毒。。。

本來就是個裸地線段樹記錄最小值。

結果誤解他題目了，。

調了三個小時

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<cstring>
  4 #include<cmath>
  5 #include<queue>
  6 #include<algorithm>
  7 #define ls k<<1
  8 #define rs k<<1|1
  9 using namespace std;
 10 const int MAXN=2000001;
 11 void read(int &n)
 12 {
 13     char c='+';int x=0;bool flag=0;
 14     while(c<'0'||c>'9')
 15     {c=getchar();if(c=='-')flag=1;}
 16     while(c>='0'&&c<='9')
 17     {x=x*10+c-48,c=getchar();}
 18     flag==1?n=-x:n=x;
 19 }
 20 int n,m,chair;
 21 int ans=-1;
 22 struct node
 23 {
 24     int l,r,w,fm;
 25 }tree[MAXN*4];
 26 void update(int k)
 27 {
 28     tree[k].w=min(tree[ls].w,tree[rs].w);
 29     
 30 }
 31 void pushdown(int k)
 32 {
 33     tree[ls].w-=tree[k].fm;
 34     tree[rs].w-=tree[k].fm;
 35     tree[ls].fm+=tree[k].fm;
 36     tree[rs].fm+=tree[k].fm;
 37     tree[k].fm=0;
 38     //cout<<"ls:"<<(ls)<<" "<<tree[ls].w<<" ";
 39     //cout<<"rs:"<<(rs)<<" "<<tree[rs].w<<" "<<endl;
 40 }
 41 void build_tree(int ll,int rr,int k)
 42 {
 43     tree[k].l=ll;tree[k].r=rr;
 44     if(ll==rr)
 45     {
 46         tree[k].w=chair;
 47         return ;
 48     }
 49     int mid=(ll+rr)>>1;
 50     build_tree(ll,mid,ls);
 51     build_tree(mid+1,rr,rs);
 52     update(k);
 53 }
 54 void interval_ask(int ll,int rr,int num,int k)
 55 {
 56     if(ll>tree[k].r||rr<tree[k].l)
 57         return ;
 58     if(ll<=tree[k].l&&tree[k].r<=rr)
 59     {
 60         if(tree[k].w<num)
 61             ans=-1;
 62         return ;
 63     }
 64     int mid=(tree[k].l+tree[k].r)>>1;
 65     if(tree[k].fm)
 66     pushdown(k);
 67     if(ll<=mid)
 68     interval_ask(ll,rr,num,ls);
 69     if(rr>mid)
 70     interval_ask(ll,rr,num,rs);
 71     if(tree[k].fm)
 72     pushdown(k);
 73 }
 74 void point_change(int pos,int v,int k)
 75 {
 76     if(pos>tree[k].r||pos<tree[k].l)
 77         return ;
 78     if(tree[k].l==tree[k].r)
 79     {
 80         tree[k].w=v;
 81         return ;
 82     }
 83     point_change(pos,v,ls);
 84     point_change(pos,v,rs);
 85     update(k);
 86 }
 87 
 88 void interval_change(int ll,int rr,int num,int k)
 89 {
 90     if(ll>tree[k].r||rr<tree[k].l)
 91         return ;
 92     if(ll<=tree[k].l&&rr>=tree[k].r)
 93     {
 94         tree[k].w-=num;
 95         tree[k].fm+=num;
 96         return ;
 97     }
 98     int mid=(tree[k].l+tree[k].r)>>1;
 99     if(tree[k].fm)
100     pushdown(k);
101     if(ll<=mid)
102     interval_change(ll,rr,num,ls);
103     if(rr>mid)
104     interval_change(ll,rr,num,rs);
105     update(k);
106 }
107 int main()
108 {
109     read(n);read(chair);read(m);
110     build_tree(1,n,1);
111     for(int i=1;i<=m;i++)
112     {
113         int l,r,num;
114         ans=1;
115         read(l);read(r);read(num);
116         r--;
117         interval_ask(l,r,num,1);
118         if(ans!=1)
119             printf("N\n");
120         else 
121         {
122             interval_change(l,r,num,1);
123             printf("T\n");    
124         }
125     }
126     return 0;
127 }