火车票订购——惨淡的通过率源于不够紧凑的数据

主要是线段树+离散化，稍微说几点😶

1. 询问规模很大(n<=10^5)，没有时间直接遍历区间，题目要求实现查询和修改区间，联想到线段树。
2. 同时车站号数值也很大(可能m>>10^5)，直接按车站号开数组空间会不够，估计很多同学卡在这了。
3. 考虑到真实存在的车站数其实不超过2n，通过离散化(对车站号排序+去重+取秩)将原来离散的车站号转化成可操作的紧凑的车站号。
4. “请求订购从a站到b站的k张票”——很多同学(比如我)可能觉得常识上火车从a车站接人上车，到达b车站了该放人下车了吧？？然而本题测试数据告诉我们：并没有，即使到了b车站他们也还在车上！
5. 此外本题还可以参考tzoj题目id3315:买火车票，不过那道题数据很小，不用做离散化。
6. 要求线段树修改区间的，懒标记能用就用，不然更新操作的时间复杂度肯定不止O(logn)，可能过不了。

   #include <cstdio>
   #include <cstring>
   #include <algorithm>
   #define MAX 100000
   
   using namespace std;
   
   int tree[MAX << 3], lazy[MAX << 3];//递归式线段树和懒标记数组
   int a[MAX], b[MAX], k[MAX];
   
   int discrete(int* a, int* b, int n) {
       int temp[MAX << 1], len = 0;
       for(int i = 0; i < n; i++) {
           temp[len++] = a[i];
           temp[len++] = b[i];
       }
       sort(temp, temp + len);
       len = unique(temp, temp + len) - temp;
       for(int i = 0; i < n; i++) {
           a[i] = lower_bound(temp, temp + len, a[i]) - temp;
           b[i] = lower_bound(temp, temp + len, b[i]) - temp;
       }
       return len;
   }
   
   int getmax(int a, int b) {
       return a >= b ? a : b;
   }
   
   void build() {
       memset(tree, 0, sizeof(tree));
       memset(lazy, 0, sizeof(lazy));
       return;
   }
   
   void pushup(int root) {
       tree[root] = getmax(tree[root << 1], tree[root << 1 | 1]);
       return;
   }
   
   void pushdown(int root) {
       if(lazy[root] == 0) return;
       tree[root << 1] += lazy[root];
       tree[root << 1 | 1] += lazy[root];
       lazy[root << 1] += lazy[root];
       lazy[root << 1 | 1] += lazy[root];
       lazy[root] = 0;
       return;
   }
   
   void update(int a, int b, int k, int l, int r, int root) {
       if(a <= l && r <= b) {
           tree[root] += k;
           lazy[root] += k;
           return;
       }
       pushdown(root);
       int mid = (l + r) >> 1;
       if(a <= mid) update(a, b, k, l, mid, root << 1);
       if(mid + 1 <= b) update(a, b, k, mid + 1, r, root << 1 | 1);
       pushup(root);
   }
   
   int query(int a, int b, int l, int r, int root) {
       int ans = 0;
       if(a <= l && r <= b) return tree[root];
       pushdown(root);
       int mid = (l + r) >> 1;
       if(a <= mid) ans = getmax(ans, query(a, b, l, mid, root << 1));
       if(mid + 1 <= b) ans = getmax(ans, query(a, b, mid + 1, r, root << 1 | 1));
       return ans;
   }
   
   int main() {
       int n = 0, m = 0, len = 0;
       while(scanf("%d%d", &n, &m) != EOF) {
           for(int i = 0; i < n; i++)
               scanf("%d%d%d", &a[i], &b[i], &k[i]);
           //建树
           build();
           //对所有车站做离散化并拿到真实的车站数
           len = discrete(a, b, n);
           for(int i = 0; i < n; i++) {
               //区间查询+区间修改
               if(query(a[i], b[i], 0, len - 1, 1) + k[i] <= m) {
                   update(a[i], b[i], k[i], 0, len - 1, 1);
                   printf("1\n");
               }
               else printf("0\n");
           }
       }
       return 0;
   }