题目大意：有$n(n\leqslant5\times10^5)$个数，有$m(m\leqslant5\times10^5)$次询问。
一次询问形如$l\;r\;s\;k\;w_1\;w_2\dots w_k：$每次询问$[l_i,r_i]$内的出现次数大于一半的数，如果没有，则为$s$。这次询问后结束后$k(\sum k\leqslant10^6)$个位置的数$w_i$变成询问答案。
题解：求大于一半的数可以用[洛谷P2397]yyy loves Maths VI (mode)来做，带修改，可以用线段树，维护区间最大的数，以及这个数比一半多了多少。但是求出来的答案只是可能的解（因为没有出现次数保证大于一半），可以用平衡树求出这个数在这个区间中出现次数，判断是否合法。修改暴力改
卡点：初值计数器赋成$-1$，导致转移出锅
C++ Code：
#include <cstdio>
#include <cctype>
//#define ONLINE_JUDGE
namespace R {
int x;
#ifdef ONLINE_JUDGE
#define M 1 << 27
char op[M], *ch;
inline void init() {fread(ch = op, 1, M, stdin);}
inline int read() {
while (isspace(*ch)) ch++;
for (x = *ch & 15, ch++; isdigit(*ch); ch++) x = x * 10 + (*ch & 15);
return x;
}
#else
char ch;
inline int read() {
ch = getchar();
while (isspace(ch)) ch = getchar();
for (x = ch & 15, ch = getchar(); isdigit(ch); ch = getchar()) x = x * 10 + (ch & 15);
return x;
}
#endif
}
using R::read; #define maxn 500010 int n, m;
int s[maxn]; namespace SgT {
struct node {
int s, cnt; //s为区间可能众数，cnt这个数比一半区间长度多多少
inline node(int __s = 0, int __cnt = 0) {s = __s, cnt = __cnt;}
inline friend node operator + (const node &lhs, const node &rhs) {
if (lhs.s == rhs.s) return node(lhs.s, lhs.cnt + rhs.cnt);
if (lhs.cnt > rhs.cnt) return node(lhs.s, lhs.cnt - rhs.cnt);
else return node(rhs.s, rhs.cnt - lhs.cnt);
}
} V[maxn << 2];
inline void update(int rt) {
V[rt] = V[rt << 1] + V[rt << 1 | 1];
} void build(int rt, int l, int r) {
if (l == r) {
V[rt] = node(s[l], 1);
return ;
}
int mid = l + r >> 1;
build(rt << 1, l, mid);
build(rt << 1 | 1, mid + 1, r);
update(rt);
} int pos, num;
void __modify(int rt, int l, int r) {
if (l == r) {
V[rt] = node(num, 1);
return ;
}
int mid = l + r >> 1;
if (pos <= mid) __modify(rt << 1, l, mid);
else __modify(rt << 1 | 1, mid + 1, r);
update(rt);
}
void modify(int __pos, int __num) {
pos = __pos, num = __num;
__modify(1, 1, n);
} int L, R;
node __query(int rt, int l, int r) {
if (L <= l && R >= r) return V[rt];
int mid = l + r >> 1;
node ans;
if (L <= mid) ans = __query(rt << 1, l, mid);
if (R > mid) ans = ans + __query(rt << 1 | 1, mid + 1, r);
return ans;
}
int query(int __L, int __R, int tg = 0) {
L = __L, R = __R;
return __query(1, 1, n).s;
}
} namespace Treap {
int root[maxn];
#define N 1000010 + maxn
int seed = 20040826;
inline int rand() {return seed *= 48271;}
int ta, tb, tmp, res; int lc[N], rc[N], pri[N], V[N], sz[N], idx;
inline int nw(int x) {
pri[++idx] = rand();
sz[idx] = 1;
V[idx] = x;
return idx;
}
inline int update(int rt) {
sz[rt] = sz[lc[rt]] + sz[rc[rt]] + 1;
return rt;
} void split(int rt, int k, int &x, int &y) {
if (!rt) x = y = 0;
else {
if (V[rt] <= k) split(rc[rt], k, rc[rt], y), x = update(rt);
else split(lc[rt], k, x, lc[rt]), y = update(rt);
}
}
int merge(int x, int y) {
if (!x || !y) return x | y;
if (pri[x] > pri[y]) {rc[x] = merge(rc[x], y); return update(x);}
else {lc[y] = merge(x, lc[y]); return update(y);}
} void insert(int &rt, int x) {
if (!rt) rt = nw(x);
else {
split(rt, x, ta, tb);
rt = merge(merge(ta, nw(x)), tb);
}
}
void erase(int &rt, int x) {
split(rt, x, ta, tb);
split(ta, x - 1, ta, tmp);
rt = merge(ta, tb);
} int gtrnk(int &rt, int x) {
split(rt, x, ta, tb);
res = sz[ta];
merge(ta, tb);
return res;
} int query(int &rt, int l, int r) {
// printf("%d %d\n", gtrnk(rt, r), gtrnk(rt, l));
return gtrnk(rt, r) - gtrnk(rt, l - 1);
}
void modify(int tg, int &before, int after) {
erase(root[before], tg);
insert(root[after], tg);
before = after;
}
#undef N
}
using Treap::root; int main() {
#ifdef ONLINE_JUDGE
R::init();
#endif
n = read(), m = read();
for (int i = 1; i <= n; i++) Treap::insert(root[s[i] = read()], i);
SgT::build(1, 1, n);
while (m --> 0) {
int l = read(), r = read(), s = read(), k = read();
int tmp = SgT::query(l, r);
int CNT = Treap::query(root[tmp], l, r);
if (CNT <= (r - l + 1 >> 1)) tmp = s;
printf("%d\n", tmp);
for (int i = 0, x; i < k; i++) {
x = read();
SgT::modify(x, tmp);
Treap::modify(x, ::s[x], tmp);
}
}
int tmp = SgT::query(1, n);
int CNT = Treap::query(root[tmp], 1, n);
if (CNT <= n >> 1) tmp = -1;
printf("%d\n", tmp);
return 0;
}