Ticket Selling(线段树区间更新)

描述

传送门:SHUOJ238

虫虫出行常常需要用到铁路购票系统,但是铁路购票系统的反应太慢了,所以虫虫打算自己重新写一个铁路购票系统。

对于一条线路,会有 $n$ 个站点,记为 $1,2,…n$,每个站点都可以上车或下车。一个旅客会向系统发起 $(l, r)$ 的申请,表示他想从第 $l$ 个站点上车,第 $r$ 个站点下车。车上只有 $k$ 个座位,车发动后,车上的人数不能超过 $k$。

现在你需要帮虫虫完成这个工作,回答每个用户是否购票成功。

输入

第一行三个整数 $n, m, k$。
接下来 $m$ 行,每行两个数字 $l, r$$(1 ≤ l < r ≤ n)$,表示这个用户想买从 $l$ 上到 $r$ 下的车票。

输出

对每个用户输出一行,表示这个用户是否购票成功。成功输出 Yes,失败输出 No

对于10%的数据,$n ≤ 10$, $m ≤ 10$
对于30%的数据,$n ≤ 1000$, $m ≤ 1000$
对于60%的数据,$n ≤ 50000$, $m ≤ 50000$
对于100%的数据,$n ≤ 100000$, $m ≤ 100000$, $0 < k < 1000000$

样例输入

1
2
3
4
5
6
5 5 2
1 5
1 3
3 4
3 5
4 5

样例输出

1
2
3
4
5
Yes
Yes
Yes
No
Yes

思路

  • 用线段树维护区间最大值即可。
  • 有个问题就是上下车的时候车上的人数是可以大于$k$的。为了解决这个问题,我们需要将每一站分两段,一段下车,一段上车。
  • 延迟更新标记的传递还是一样的套路。

代码

1
2
3
4
#define lson rt << 1
#define rson rt << 1 | 1
#define Lson l, m, lson
#define Rson m + 1, r, rson
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
#include <bits/stdc++.h>
using namespace std;
#define clr(a,x) memset(a, x, sizeof(a))
#define mp(x,y) make_pair(x,y)
#define pb(x) push_back(x)
#define X first
#define Y second
#define fastin ios_base::sync_with_stdio(0);cin.tie(0);
typedef long long ll;
typedef long double ld;
typedef pair<int, int> PII;
typedef vector<int> VI;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7;
const double eps = 1e-6;

const int maxn = 2e5 + 5;
int maxv[maxn << 2], addv[maxn << 2];

void pushup(int rt)
{
maxv[rt] = max(maxv[lson], maxv[rson]);
}

void pushdown(int rt)
{
if (addv[rt] == 0) return;
addv[lson] += addv[rt];
addv[rson] += addv[rt];
maxv[lson] += addv[rt];
maxv[rson] += addv[rt];
addv[rt] = 0;
}

void build(int l, int r, int rt)
{
maxv[rt] = addv[rt] = 0;
if (l == r) return;
int m = (l + r) >> 1;
build(Lson);
build(Rson);
}

void update(int L, int R , int add, int l, int r, int rt)
{
if (L <= l && r <= R)
{
addv[rt] += add;
maxv[rt] += add;
return;
}
pushdown(rt);
int m = (l + r) >> 1;
if (L <= m) update(L, R, add, Lson);
if (m < R) update(L, R, add, Rson);
pushup(rt);
}

int query(int L, int R, int l, int r, int rt)
{
if (L <= l && r <= R) return maxv[rt];
pushdown(rt);
int m = (l + r) >> 1, ans = 0;
if (L <= m) ans = max(ans, query(L, R, Lson));
if (m < R) ans = max(ans, query(L, R, Rson));
return ans;
}

int main()
{
#ifndef ONLINE_JUDGE
freopen("1.in", "r", stdin);
freopen("1.out", "w", stdout);
#endif
int n, m, k;
while (~scanf("%d%d%d", &n, &m, &k))
{
n <<= 1;
build(1, n, 1);
while (m--)
{
int l, r;
scanf("%d%d", &l, &r);
l <<= 1, r--, r <<= 1;
if (query(l, r, 1, n, 1) < k)
{
puts("Yes");
update(l, r, 1, 1, n, 1);
}
else
puts("No");
}
}
return 0;
}
捐助作者