abcdeffa's Blog

当局者迷，旁观者清。

0%

GMOJ S3740 【电源插排】

发表于 更新于

Description

一个房间内有 $n$ 个空位，现在要进行 $T$ 次操作。

这 $T$ 个操作分为两类，第一类是进出房间，即改变他的位置状态，一个人会选择在最靠右的最长连续空位段中间中靠右的位置；第二类是询问在编号为 $l$ 到 $r$ 的座位中，一共坐了多少个人。每个人有他自己独特的编号，编号在 1 到 $10^9$ 之间。

Solution

考虑使用 线段树 来解题。

我们考虑维护一个区间的：

  1. 此区间内最大区间的长度
  2. 此区间内最大区间的起始位置
  3. 从左向右扩展的最大长度
  4. 从右向左扩展的最大长度
  5. 此区间内被占据的个数

以上内容摘自 @Felix-Lee 的博客。

至此，操作可轻松完成。

Code

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
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
#include <cstdio>
#define mod 1000007
#define maxN 1000010
struct tree{ int lc, rc, Mcd, Mst, LtR, RtL, sum; } a[maxN << 2];
int len = 0;
int hash[mod], b[mod], g[mod];
void build (int now, int l, int r)
{
	a[now].Mcd = r - l + 1;
	a[now].Mst = l;
	a[now].LtR = r - l + 1;
	a[now].RtL = r - l + 1;
	a[now].sum = 0;
}
int Hash (int x)
{
	int y = x % mod;
	while(hash[y] && hash[y] != x)
	{
		y++;
		y %= mod;
	}
	return y;
}
int query (int now, int l, int r, int L, int R)
{
	if(l == L && r == R)
	{
		return a[now].sum;
	}
	int mid = (l + r) >> 1;
	if(!a[now].lc)
	{
		a[now].lc = len + 1;
		build(++len, l, mid); 
	}
	if(!a[now].rc)
	{
		a[now].rc = len + 1;
		build(++len, mid + 1, r);
	}
	if(R <= mid)
	{
		return query(a[now].lc, l, mid, L, R);
	}
	else if(mid + 1 <= L)
	{
		return query(a[now].rc, mid + 1, r, L, R);
	}
	else
	{
		int A = query(a[now].lc, l, mid, L, mid);
		int B = query(a[now].rc, mid + 1, r, mid + 1, R);
		return A + B;
	}
}
void change (int now, int l, int r, int x, int t)
{
	if(l == r)
	{
		a[now].sum += t;
		if(t > 0)
		{
			a[now].Mcd = 0;
			a[now].Mst = 0;
			a[now].LtR = 0;
			a[now].RtL = 0;
		}
		else
		{
			a[now].Mcd = 1;
			a[now].Mst = l;
			a[now].LtR = 1;
			a[now].RtL = 1;
		}
		return ;
	}
	int mid = (l + r) >> 1;
	if(!a[now].lc)
	{
		a[now].lc = len + 1;
		build(++len, l, mid);
	}
	if(!a[now].rc)
	{
		a[now].rc = len + 1;
		build(++len, mid + 1, r);
	}
	if(x <= mid)
	{
		change(a[now].lc, l, mid, x, t);
	}
	else
	{
		change(a[now].rc, mid + 1, r, x, t);
	}
	a[now].sum = a[a[now].lc].sum + a[a[now].rc].sum;
	a[now].LtR = a[a[now].lc].LtR;
	if(a[a[now].lc].LtR == mid - l + 1)
	{
		a[now].LtR += a[a[now].rc].LtR;
	}
	a[now].RtL = a[a[now].rc].RtL;
	if(a[a[now].rc].RtL == r - mid)
	{
		a[now].RtL += a[a[now].lc].RtL;
	}
	if(a[a[now].lc].Mcd > a[a[now].rc].Mcd)
	{
		a[now].Mcd = a[a[now].lc].Mcd;
		a[now].Mst = a[a[now].lc].Mst;
	}
	else
	{
		a[now].Mcd = a[a[now].rc].Mcd;
		a[now].Mst = a[a[now].rc].Mst;
	}
	int A = (a[a[now].lc].RtL + a[a[now].rc].LtR > a[now].Mcd);
	int B = (a[a[now].lc].RtL + a[a[now].rc].LtR == a[now].Mcd);
	int C = mid - a[a[now].lc].RtL + 1 > a[now].Mst;
	if(A | (B & C))
	{
		a[now].Mcd = a[a[now].lc].RtL + a[a[now].rc].LtR;
		a[now].Mst = mid - a[a[now].lc].RtL + 1;
	}
}
int main ()
{
	int n = 0, T = 0;
	scanf("%d %d", &n, &T);
	build(++len, 1, n);
	while(T--)
	{
		int x = 0;
		scanf("%d", &x);
		if(!x)
		{
			int l = 0, r = 0;
			scanf("%d %d", &l, &r);
			printf("%d\n", query(1, 1, n, l, r));
		}
		else
		{
			int p = Hash(x);
			if(!hash[p])
			{
				hash[p] = x;
			}
			if(!b[p])
			{
				b[p] = true;
				g[p] = a[1].Mst + (a[1].Mcd >> 1);
				change(1, 1, n, g[p], 1);
			}
			else
			{
				change(1, 1, n, g[p], -1);
				b[p] = g[p] = 0;
			}
		}
	}
	return 0;
}