P8856 [POI2002] 火车线路 题解

· · 题解

解题思路

不难看出一个起点到终点的订购很像区间加，因此不难联想到线段树。

对于一次订购，我们尝试将 [O, D - 1] 这个区间加上 N，然后判断区间最大值是否超过了火车的座位数 S，若超过了就将 N 减回去并输出 N，否则保留这个操作，输出 T。

为什么是 [O, D - 1] 呢？因为到了终点站这次订票的座位就空出来了，相当于没有受到有人订票的影响。不然就像我第一次交一样只有 32 分。

Fake AC Code

#include <bits/stdc++.h>
using namespace std;
const int N = 60005;
int n, lim, q, dat[N << 2], tg[N << 2];

inline void pushup(int p){dat[p] = max(dat[p << 1], dat[p << 1 | 1]);}

inline void pushdown(int p, int l, int r){
    if (tg[p]){
        dat[p << 1] += tg[p]; dat[p << 1 | 1] += tg[p];
        tg[p << 1] += tg[p]; tg[p << 1 | 1] += tg[p];
        tg[p] = 0;
    }
}

void update(int p, int l, int r, int lpos, int rpos, int k){
    if (l > rpos || r < lpos) return;
    if (lpos <= l && r <= rpos){
        dat[p] += k;
        tg[p] += k;
        return;
    } 
    pushdown(p, l, r);
    int mid = (l + r) >> 1;
    update(p << 1, l, mid, lpos, rpos, k); update(p << 1 | 1, mid + 1, r, lpos, rpos, k);
    pushup(p); 
} 

int query(int p, int l, int r, int lpos, int rpos){
    if (l > rpos || r < lpos) return -2e9;
    if (lpos <= l && r <= rpos) return dat[p];
    pushdown(p, l, r);
    int mid = (l + r) >> 1;
    return max(query(p << 1, l, mid, lpos, rpos), query(p << 1 | 1, mid + 1, r, lpos, rpos)); 
}

int main(){
    scanf("%d%d%d", &n, &lim, &q);
    int l, r, x;
    while (q--){
        scanf("%d%d%d", &l, &r, &x);
        update(1, 1, n, l, r - 1, x);
        if (query(1, 1, n, l, r - 1) > lim){
            update(1, 1, n, l, r - 1, -x);
            printf("N\n");
        }
        else printf("T\n");
    }
    return 0;
}

先别着急复制

因为这道题的毒瘤时限只有 100ms，上面这份代码在我交的时候需要吸氧才能稳过，不然测试点 #10 会有 120ms 左右。

那么我们怎么不开 O2 通过呢？我们发现 update 应该没啥可以优化的了，但是每次真的都需要 query 吗？显然不用。我们只需要考虑整个数列中有没有大于火车座位数量 S 的值就可以了，而这个值就在 dat[1] 中，因此 query 就优化到了 O(1)，可以通过。

新的关键部分

int main(){
    while (q--){
        scanf("%d%d%d", &l, &r, &x);
        update(1, 1, n, l, r - 1, x);
        if (dat[1] > lim){//query函数可以直接不定义了
            update(1, 1, n, l, r - 1, -x);
            printf("N\n");
        }
        else printf("T\n");
    }
}

其实还有一种方法就是保留 query，每次先判断本次订购区间的最大值加上本次要订购的数量是否超过了总座位数，没超过再更新，因为感性认为 T 的个数大概率是少于 N 的，所以效率应该会更高。