【题目大意】
一个$n$个数的序列，$m$次操作，每次选择一段区间$[l, r]$，求出$[l, r]$中出现超过一半的数。
如果没有超过一半的数，那么就把答案钦定为$s$，每次会有$k$个数进行改变，给出下标，改变成当前的答案$s$。
$n, m \leq 5*10^5, \sum k\leq 10^6$
By FJSDFZ ditoly
【题解】
用这题的方法进行线段树操作即可：http://www.cnblogs.com/galaxies/p/20170602_c.html
但是这样需要验证是否可行，那么问题变成待修改的询问$[l, r]$区间内$x$的出现次数。
如果没有修改，我会分块！
修改就写个平衡树（开始想STL发现set不支持iterator减法，就gg了）
然后慢的要死。（论不会treap的危害）
后来一气之下找了pb_ds::tree来用。
# include <ext/pb_ds/assoc_container.hpp>
# include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
tree <int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> S[M];
每次只要调用order_of_key(x)即可，注意这个操作是右开区间，所以本题中可能需要些许变换。
# include <stdio.h>
# include <string.h>
# include <iostream>
# include <algorithm>
// # include <bits/stdc++.h> using namespace std; typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
const int M = 5e5 + ;
const int mod = 1e9+; inline int getint() {
int x = ; char ch = getchar();
while(!isdigit(ch)) ch = getchar();
while(isdigit(ch)) x = (x<<) + (x<<) + ch - '', ch = getchar();
return x;
} # define gi getint() int n, a[M]; struct node {
int w, t;
node() {}
node(int w, int t) : w(w), t(t) {}
friend node operator + (node a, node b) {
if(a.w == b.w) return node(a.w, a.t + b.t);
if(a.t >= b.t) return node(a.w, a.t - b.t);
else return node(b.w, b.t - a.t);
}
}; /*
int rt[M];
struct Splay {
int ch[M][2], fa[M], val[M], s[M];
inline void up(int x) {
if(!x) return ;
s[x] = 1 + s[ch[x][0]] + s[ch[x][1]];
}
inline void rotate(int x, int &rt) {
int y = fa[x], z = fa[y], ls = ch[y][1] == x, rs = ls^1;
if(rt == y) rt = x;
else ch[z][ch[z][1] == y] = x;
fa[ch[x][rs]] = y, fa[y] = x, fa[x] = z;
ch[y][ls] = ch[x][rs]; ch[x][rs] = y;
up(y), up(x);
}
inline void splay(int x, int &rt) {
while(x != rt) {
int y = fa[x], z = fa[y];
if(y != rt) {
if((ch[z][0] == y) ^ (ch[y][0] == x)) rotate(x, rt);
else rotate(y, rt);
}
rotate(x, rt);
}
} inline int find(int x, int pos) {
if(pos == val[x]) return x;
if(pos < val[x]) return find(ch[x][0], pos);
else return find(ch[x][1], pos);
} inline int gmax(int x) {
while(ch[x][1]) x = ch[x][1];
return x;
} inline int del(int &rt, int pos) {
int x = find(rt, pos);
splay(x, rt);
if(!ch[x][0]) {
rt = ch[x][1]; fa[rt] = 0; ch[x][1] = 0;
return x;
}
if(!ch[x][1]) {
rt = ch[x][0]; fa[rt] = 0; ch[x][0] = 0;
return x;
}
int y = gmax(ch[x][0]); splay(y, ch[x][0]);
rt = y; ch[y][1] = ch[x][1]; fa[ch[x][1]] = y;
ch[x][0] = ch[x][1] = 0; fa[y] = 0;
up(y);
return x;
} inline void ins(int &x, int y, int pos, int id) {
if(!x) {
x = id; fa[x] = y; val[x] = pos; s[x] = 1; ch[x][0] = ch[x][1] = 0;
return ;
}
if(pos < val[x]) ins(ch[x][0], x, pos, id);
else ins(ch[x][1], x, pos, id);
up(x);
} inline void Ins(int &rt, int pos, int id) {
ins(rt, 0, pos, id);
splay(id, rt);
} inline int rank(int x, int d) {
if(!x) return 0;
if(d < val[x]) return rank(ch[x][0], d);
else return s[ch[x][0]] + 1 + rank(ch[x][1], d);
} inline void DEBUG(int x) {
if(!x) return ;
DEBUG(ch[x][0]);
printf("x = %d, ls = %d, rs = %d, pos = %d, sz = %d\n", x, ch[x][0], ch[x][1], val[x], s[x]);
DEBUG(ch[x][1]);
} inline void debug() {
for (int i=1; i<=5; ++i) {
printf("rt %d ======================\n", i);
DEBUG(rt[i]);
}
puts("\n");
}
}S;
*/ # include <ext/pb_ds/assoc_container.hpp>
# include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
tree <int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> S[M]; struct SMT {
node w[M << ];
# define ls (x<<)
# define rs (x<<|)
inline void up(int x) {
w[x] = w[ls] + w[rs];
}
inline void build(int x, int l, int r) {
if(l == r) {
w[x] = node(a[l], );
return ;
}
int mid = l+r>>;
build(ls, l, mid), build(rs, mid+, r);
up(x);
}
inline void edt(int x, int l, int r, int ps, int d) {
if(l == r) {
S[w[x].w].erase(l);
w[x] = node(d, );
S[d].insert(l);
return ;
}
int mid = l+r>>;
if(ps <= mid) edt(ls, l, mid, ps, d);
else edt(rs, mid+, r, ps, d);
up(x);
}
inline node query(int x, int l, int r, int L, int R) {
if(L <= l && r <= R) return w[x];
int mid = l+r>>;
if(R <= mid) return query(ls, l, mid, L, R);
else if(L > mid) return query(rs, mid+, r, L, R);
else return query(ls, l, mid, L, mid) + query(rs, mid+, r, mid+, R);
}
inline void debug(int x, int l, int r) {
printf("x = %d, [%d, %d], w[x] = {%d, %d}\n", x, l, r, w[x].w, w[x].t);
if(l == r) return ;
int mid = l+r>>;
debug(ls, l, mid);
debug(rs, mid+, r);
}
# undef ls
# undef rs
}T; inline bool check(int l, int r, int d) {
int times = S[d].order_of_key(r+) - S[d].order_of_key(l);
// cout << "times = " << times << endl;
if(times <= (r-l+)/) return false;
return true;
} int main() {
freopen("president.in", "r", stdin);
freopen("president.out", "w", stdout);
n = gi; int Q = gi;
for (int i=; i<=n; ++i) {
a[i] = gi;
S[a[i]].insert(i);
}
T.build(, , n);
int l, r, s, k, leader; node ans;
while(Q--) {
if(Q % == ) cerr << Q << endl;
// S.debug();
l = gi, r = gi, s = gi, k = gi;
ans = T.query(, , n, l, r);
if(check(l, r, ans.w)) leader = ans.w;
else leader = s;
for (int i=, t; i<=k; ++i) {
t = gi;
T.edt(, , n, t, leader);
}
printf("%d\n", leader);
// T.debug(1, 1, n);
}
ans = T.query(, , n, , n);
if(check(, n, ans.w)) printf("%d\n", ans.w);
else puts("-1");
return ;
}
注释里面是平衡树。。T得不要不要的。。
复杂度都是$O((n + m + \sum K) log n)$