Description：
秋之国共有n个人，分别编号为1,2,…,n，一开始每个人都投了一票，范围1~n，表示支持对应编号的人当总统。共有m次预选，每次选取编号[$l_i$,$r_i$]内的选民展开小规模预选，在该区间内获得超过区间大小一半的票的人获胜，如果没有人获胜，则由小C钦定一位候选者获得此次预选的胜利（获胜者可以不在该区间内），每次预选的结果需要公布出来，并且每次会有$k_i$个人决定将票改投向该次预选的获胜者。全部预选结束后，公布最后成为总统的候选人。
Input：
第一行两个整数n,m，表示秋之国人数和预选次数。
第二行n个整数，分别表示编号1~n的选民投的票。
接下来m行，每行先有4个整数，分别表示$l_i,r_i,s_i,k_i，s_i$表示若此次预选无人胜选，视作编号为$s_i$的人获得胜利，接下来$k_i$个整数，分别表示决定改投的选民。
Output：
共m+1行，前m行表示各次预选的结果，最后一行表示最后成为总统的候选人，若最后仍无人胜选，输出-1。
Analysis：
考虑如下操作：
对于一列数，从头到尾开始扫描，记录num与cnt。 初始num=cnt=0，每次加入一个新的数字时，如果这个数字与num相同，则++cnt。如果不相同，如cnt>0则–cnt，否则num被替换为现在的数字，cnt=1
那么如果有答案的话，答案一定是最后的num。可以发现这个信息可以被区间维护（相同相加，不同相减区大者）。虽然出来的信息比较奇怪，但是如果在本区间有答案的话，一定是最后的num
接下来的工作是处理num在某个区间中出现了多少次，比较好的方法是用splay。对于每一个候选者建一棵splay，节点就是投票者(其实是n棵splay共用n个节点了），于是就可以求出某一区间中某人被投票的次数了。至于修改，就是删点和加点了。
Thoughts：
１．本题思维比较巧妙，某些时候我们只需保证答案的正确性而中间的结果似乎不那么重要(那个处理出现次数大于一半的做法很巧妙)
２．个人觉得splay的用法很好，多棵splay可以共用节点（维护区间出现次数信息并支持修改）
Code：
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<set>
#define LL long long
#define For(i, a, b) for(int i = (a); i <= (int)(b); ++i)
using namespace std;
#define N (500000+5)
#define Ite set<int>::iterator
char chr;
inline void Read(int &x){
chr = getchar();
while(chr < '0' || chr > '9') chr = getchar();
x = 0;
while(chr >= '0' && chr <= '9'){
x = (x<<1)+(x<<3)+(chr^'0'); chr = getchar();
}
}
inline void Write(int x){
if(!x) return;
Write(x/10);
putchar(x%10+'0');
}
struct node{
int v, cnt;
node operator +(const node &rhs)const{
if(v == rhs.v) return (node){v, cnt+rhs.cnt};
if(cnt > rhs.cnt) return (node){v, cnt-rhs.cnt};
if(cnt < rhs.cnt) return (node){rhs.v, rhs.cnt-cnt};
return (node){!v? rhs.v: v, 0};
}
};
int ql, qr, ch[N][2], fa[N], siz[N], my[N];
#define lc (o<<1)
#define rc (o<<1|1)
#define mid ((L+R)>>1)
//struct SegTree{
node tr[N<<2];
inline void Build(int o, int L, int R){
if(L == R){tr[o] = (node){my[L], 1}; return;}
Build(lc, L, mid); Build(rc, mid+1, R);
tr[o] = tr[lc]+tr[rc];
}
inline void Modify(int o, int L, int R, int pos){
if(L == R){tr[o] = (node){my[L], 1}; return;}
if(pos <= mid) Modify(lc, L, mid, pos);
else Modify(rc, mid+1, R, pos);
tr[o] = tr[lc]+tr[rc];
}
inline node Query(int o, int L, int R){
if(ql <= L && qr >= R) return tr[o];
node ret = (node){0, 0};
if(ql <= mid) ret = ret+Query(lc, L, mid);
if(qr > mid) ret = ret+Query(rc, mid+1, R);
return ret;
}
//}ST;
#undef lc
#undef rc
#undef mid
Ite it;
#define lc ch[o][0]
#define rc ch[o][1]
struct SPLAY{
int rt;
set<int> mem;
inline void maintain(int o){
siz[o] = 1;
if(lc) siz[o] += siz[lc]; if(rc) siz[o] += siz[rc];
}
inline void Rotate(int o){
int f = fa[o], g = fa[f];
int c = o==ch[f][1];
if(g) ch[g][ch[g][1]==f] = o;
fa[o] = g; fa[f] = o; fa[ch[o][c^1]] = f;
ch[f][c] = ch[o][c^1]; ch[o][c^1] = f;
maintain(f); maintain(o);
}
inline void Splay(int x, int aim){
int f, g;
while(fa[x] != aim){
f = fa[x]; g = fa[f];
if(g != aim) Rotate(f);
Rotate(x);
}
if(!aim) rt = x;
}
inline void Insert(int now){
siz[now] = 1; mem.insert(now);
if(!rt){rt = now; return;}
int x = rt;
while(ch[x][now>x]) x = ch[x][now>x];
ch[x][now>x] = now; fa[now] = x;
Splay(now, 0);
}
inline void Del(int o){
mem.erase(o);
if(o == rt && siz[o] == 1){rt = 0; siz[o] = 0; return;}
while(siz[lc] || siz[rc]){
if((siz[lc] < siz[rc]&&siz[lc]) || !siz[rc]){
if(o==rt) rt = lc; Rotate(lc);
}else{
if(o==rt) rt = rc; Rotate(rc);
}
}
int f = fa[o];
ch[f][ch[f][1]==o] = 0; fa[o] = 0; siz[o] = 0;
while(f){maintain(f); f = fa[f];}
}
inline int count(int Min, int Max){
int u = *mem.lower_bound(Min);
it = mem.upper_bound(Max); if(*it != Max) --it;
int v = *it;
if(u > v) return 0; if(u == v) return 1;
Splay(u, 0); Splay(v, u);
return siz[ch[v][0]]+2;
}
}spl[N];
#undef lc
#undef rc
int main(){
#ifndef ONLINE_JUDGE
freopen("test.in", "r", stdin);
freopen("test.out", "w", stdout);
#endif
int n, m, s, k;
Read(n); Read(m);
For(i, 1, n){
Read(my[i]); spl[my[i]].Insert(i);
}
Build(1, 1, n);
node now;
int half, pre, np;
while(m--){
Read(ql); Read(qr); Read(s); Read(k);
half = (qr-ql+1)>>1, now = Query(1, 1, n);
if(spl[now.v].count(ql, qr) > half) pre = now.v;
else pre = s;
For(i, 1, k){
Read(np); if(my[np] == pre) continue;
spl[my[np]].Del(np); spl[my[np]=pre].Insert(np);
Modify(1, 1, n, np);
}
Write(pre); puts("");
}
half = (n>>1);
For(i, 1, n)
if(siz[spl[i].rt]>half){
Write(i); puts(""); return 0;
}
puts("-1");
return 0;
}