自动搬运

查看原文

来自洛谷，原作者为

	lrqlrq250 AFOed, さよなら

搬运于2025-08-24 22:43:09，当前版本为作者最后更新于2022-11-18 18:34:59，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

解题思路

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

对于一次订购，我们尝试将 $[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 的，所以效率应该会更高。