题目链接：传送门

Description

秋之国共有nn个人，分别编号为1,2,...,n1,2,...,n 一开始每个人都投了一票，范围1−n1-n，表示支持对应编号的人当总统。

共有mm次预选，每次选取编号[li,ri][l_i,r_i]内的选民展开小规模预选，在该区间内获得超过区间大小一半的票的人获胜。如果没有人获胜，则由小C钦定一位候选者获得此次预选的胜利（获胜者可以不在该区间内）

每次预选的结果需要公布出来，并且每次会有kik_i个人决定将票改投向该次预选的获胜者。全部预选结束后，公布最后成为总统的候选人。

Constraints

1≤n,m≤500,000,∑ki≤106,1≤li≤ri≤n,1≤si≤n1\le n,m\le 500,000,\sum k_i\le 10^6, 1\le l_i\le r_i \le n, 1\le s_i \le n

Input

第一行两个整数n,mn,m，表示秋之国人数和预选次数。

第二行nn个整数，分别表示编号1−n1-n的选民投的票。

接下来mm行，每行先有4个整数，分别表示li,ri,si,kil_i,r_i,s_i,k_i，sis_i表示若此次预选无人胜选，视作编号为sis_i的人获得胜利，接下来kik_i个整数，分别表示决定改投的选民。

Output

共m+1m+1行，前mm行表示各次预选的结果，最后一行表示最后成为总统的候选人，若最后仍无人胜选，输出-1。

Sample Input

5 4

1 2 3 4 5

1 2 1 1 3

5 5 1 2 2 4

2 4 2 0

3 4 2 1 4

Sample Output

1

5

5

2

-1

Solution

首先，过半众数的求法在BZOJ2456就有提到

可以记录val表示当前最可能为众数的那个数，cnt表示这个数当前出现了多少次

碰到一个数，如果它和val相同，则cnt++，否则如果cnt==0那么val=当前这个数，否则cnt--

这个办法可以快速求出过半众数

同理，这个方法也可以扩展到这道题上来，显然val和cnt这两个信息能够合并，我们只需要用线段树维护即可

但是这样求出来的val只是最有可能的那个一个值，无法判断它到底有没有过半

那么就需要用一个Splay来维护每个人的得票信息，具体来说就是每个人开一个Splay，里面存所有选了他的人的信息，然后只需要支持插入删除和查询权值在l−rl-r之间的数的个数即可

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
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
#include <bits/stdc++.h>

#define x first
#define y second
#define x1 X1 
#define x2 X2
#define y1 Y1
#define y2 Y2
#define mp make_pair
#define pb push_back

using namespace std;

typedef long long LL;
typedef pair<int, int> pii;

template <typename T> inline int Chkmax (T &a, T b) {return a < b ? a = b, 1 : 0;}
template <typename T> inline int Chkmin (T &a, T b) {return a > b ? a = b, 1 : 0;}
inline int read ()
{
	int sum = 0, fl = 1; char ch = getchar();
	for (; !isdigit(ch); ch = getchar()) if (ch == '-') fl = -1;
	for (; isdigit(ch); ch = getchar()) sum = (sum << 3) + (sum << 1) + ch - '0';
	return sum * fl;
}

const int Maxn = 500000 + 100;

int N, M;

int A[Maxn];

namespace SEG
{
#define ls Tree[root << 1]
#define rs Tree[root << 1 | 1]
#define lson root << 1, l, mid
#define rson root << 1 | 1, mid + 1, r
	struct tree
	{
		int cnt, val;
	}Tree[Maxn << 2];
	inline tree merge (tree x, tree y)
	{
		tree tmp;
		if (x.val == y.val) tmp.cnt = x.cnt + y.cnt;
		else tmp.cnt = abs(x.cnt - y.cnt);
		tmp.val = x.cnt > y.cnt ? x.val : y.val;
/**/	return tmp;
	}

	inline void push_up (int root) { Tree[root] = merge (Tree[root << 1], Tree[root << 1 | 1]); }

	inline void build (int root, int l, int r)
	{
		if (l == r) { Tree[root].cnt = 1, Tree[root].val = A[l]; return ; }
		int mid = l + r >> 1;
		build (lson), build (rson);
		push_up (root);
	}

	inline void modify (int root, int l, int r, int x, int v)
	{
		if (l == r) { Tree[root].val = v; return ; }
		int mid = l + r >> 1;
		if (x <= mid) modify (lson, x, v);
		else modify (rson, x, v);
		push_up (root);
	}

	inline tree query (int root, int l, int r, int x, int y)
	{
		if (x <= l && r <= y) return Tree[root];
		int mid = l + r >> 1; tree ans;
		if (x > mid) return query (rson, x, y);
		else if (y <= mid) return query (lson, x, y);
		return merge (query (lson, x, y), query (rson, x, y));
	}
#undef ls
#undef rs
#undef lson
#undef rson
}

struct tree
{
	int val, ch[2], size, fa;
}Tree[2000000 + 100];
int cnt;

struct Splay
{
	int root;
	inline void push_up (int root) { Tree[root].size = Tree[Tree[root].ch[0]].size + Tree[Tree[root].ch[1]].size + 1; }
	inline int judge_dir (int x) { return Tree[Tree[x].fa].ch[1] == x; }
	inline void connect (int x, int f, int dir) { Tree[x].fa = f; Tree[f].ch[dir] = x; }
	inline void newnode (int val, int f, int dir) { Tree[++cnt].size = 1; Tree[cnt].val = val; connect (cnt, f, dir); }

	inline void rotate (int x)
	{
		int f = Tree[x].fa, anc = Tree[f].fa, dirx = judge_dir(x), dirf = judge_dir(f);
		connect (Tree[x].ch[dirx ^ 1], f, dirx);
		connect (f, x, dirx ^ 1);
		connect (x, anc, dirf);
		push_up(f), push_up(x);
	}

	inline void splay (int x, int y)
	{
/**/	while (Tree[x].fa != y) /*差点写错...*/
		{
			int f = Tree[x].fa, dirx = judge_dir(x), dirf = judge_dir(f), anc = Tree[f].fa;
			if (anc == y) rotate(x);
			else if (dirx == dirf) rotate(f), rotate(x);
			else rotate(x), rotate(x);
		}
/**/	if (!y) root = x;
	}

	inline void insert_or_erase (int val)
	{
		if (!root) { newnode (val, 0, 0); root = cnt; return ; }
		int now = root;
		while (1)
		{
			int dir = Tree[now].val <= val;
			if (Tree[now].val == val)
			{
				int x = now;
				splay (x, 0);
				if (!Tree[x].ch[0]) { root = Tree[x].ch[1]; Tree[Tree[x].ch[1]].fa = 0; return ; }
				now = Tree[x].ch[0];
				while (Tree[now].ch[1]) now = Tree[now].ch[1];
				splay (now, x); connect (Tree[x].ch[1], now, 1);
				root = now; Tree[now].fa = 0;
				push_up(now);
				return ;
			}
			if (!Tree[now].ch[dir]) { newnode (val, now, dir); splay (cnt, 0); return ; }
			now = Tree[now].ch[dir];
		}
	}

	inline int find_val (int val)
	{
		int now = root;
		while (1)
		{
			int dir = Tree[now].val < val;
			if (Tree[now].val == val || !Tree[now].ch[dir]) return now;
			now = Tree[now].ch[dir];
		}
	}

	inline int query (int l, int r)
	{
		if (!root) return 0;
		int x = find_val(l);
		splay (x, 0);
		if (Tree[x].val < l && Tree[x].ch[1]) { x = Tree[x].ch[1]; while (Tree[x].ch[0]) x = Tree[x].ch[0]; splay(x, 0); }
		int tmp = Tree[Tree[x].ch[0]].size + (Tree[x].val < l);
		x = find_val(r);
		splay (x, 0);
		if (Tree[x].val > r && Tree[x].ch[0]) { x = Tree[x].ch[0]; while (Tree[x].ch[1]) x = Tree[x].ch[1]; splay(x, 0); }
		return Tree[Tree[x].ch[0]].size + (Tree[x].val <= r) - tmp;
	}

}S[Maxn];

int main()
{
#ifdef hk_cnyali
	freopen("A.in", "r", stdin);
	freopen("A.out", "w", stdout);
#endif
	N = read(), M = read();
	for (int i = 1; i <= N; ++i)
	{
		A[i] = read();
		S[A[i]].insert_or_erase(i);
	}
	SEG :: build (1, 1, N);
	while (M--)
	{
		int l = read(), r = read(), s = read(), k = read();
		int now = SEG :: query (1, 1, N, l, r).val;
		int sum = S[now].query(l, r);
		if (sum * 2 <= (r - l + 1)) now = s;
		printf("%d\n", now);
		for (int i = 1; i <= k; ++i)
		{
			int x = read();
			SEG :: modify (1, 1, N, x, now);
			S[A[x]].insert_or_erase(x);
			A[x] = now;
			S[A[x]].insert_or_erase(x);
		}
	}
	int now = SEG :: query (1, 1, N, 1, N).val;
	int sum = S[now].query(1, N);
	if (sum * 2 <= N) cout<<-1<<endl;
	else cout<<now<<endl;
	return 0;
}

Debug

  • 49L: 记得return东西，一开始忘记return了。。。
  • 110L: 一开始写成了x!=y，不过写着写着就发现了，以后要注意
  • 117L: 要记得设root