题目描述

黑恶势力的反攻计划被小C成功摧毁,黑恶势力只好投降。秋之国的人民解放了,举国欢庆。此时,原秋之国总统因没能守护好国土,申请辞职,并请秋之国人民的大救星小C钦定下一任。作为一名民主人士,小C决定举行全民大选来决定下一任。为了使最后成为总统的人得到绝大多数人认同,小C认为,一个人必须获得超过全部人总数的一半的票数才能成为总统。如果不存在符合条件的候选人,小C只好自己来当临时大总统。为了尽可能避免这种情况,小C决定先进行几次小规模预选,根据预选的情况,选民可以重新决定自己选票的去向。由于秋之国人数较多,统计投票结果和选票变更也成为了麻烦的事情,小C找到了你,让你帮他解决这个问题。
【问题描述】秋之国共有n个人,分别编号为1,2,…,n,一开始每个人都投了一票,范围1~n,表示支持对应编号的人当总统。共有m次预选,每次选取编号[li,ri]内的选民展开小规模预选,在该区间内获得超过区间大小一半的票的人获胜,如果没有人获胜,则由小C钦定一位候选者获得此次预选的胜利(获胜者可以不在该区间内),每次预选的结果需要公布出来,并且每次会有ki个人决定将票改投向该次预选的获胜者。全部预选结束后,公布最后成为总统的候选人

输入

第一行两个整数n,m,表示秋之国人数和预选次数。
第二行n个整数,分别表示编号1~n的选民投的票。
接下来m行,每行先有4个整数,分别表示li,ri,si,ki,si表示若此次预选无人胜选,视作编号为si的人获得胜利
接下来ki个整数,分别表示决定改投的选民。
1<=n,m<=500,000,Σki<=1,000,000,1<=li<=ri<=n,1<=si<=n。

输出

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

样例输入

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

样例输出

1
5
5
2
-1


题解

随机化+线段树

考虑如果区间中一个数的出现次数等于区间长度的一半,那么期望随机找两次即可找到该数。

所以理论上看,每次随机找20次,完全正确地处理500000个询问的概率约为0.62。而实际上由于数据水,随机15次即可AC。

然后就是找某数在区间中出现的次数,直接对每个数开一棵线段树即可。

时间复杂度$O(15n\log n)$,实际上本题很卡时(卡随机化),需要使用结构体写线段树才可以卡过。

#include <cstdio>
#include <cstdlib>
#include <algorithm>
#define N 500010
#define lson l , mid , a[x].ls
#define rson mid + 1 , r , a[x].rs
using namespace std;
struct data
{
int ls , rs , si;
}a[N * 60];
int w[N] , root[N] , tot;
inline int read()
{
int ret = 0; char ch = getchar();
while(ch < '0' || ch > '9') ch = getchar();
while(ch >= '0' && ch <= '9') ret = ret * 10 + ch - '0' , ch = getchar();
return ret;
}
void update(int p , int v , int l , int r , int &x)
{
if(!x) x = ++tot;
a[x].si += v;
if(l == r) return;
int mid = (l + r) >> 1;
if(p <= mid) update(p , v , lson);
else update(p , v , rson);
}
int query(int b , int e , int l , int r , int x)
{
if(!x) return 0;
if(b <= l && r <= e) return a[x].si;
int mid = (l + r) >> 1 , ans = 0;
if(b <= mid) ans += query(b , e , lson);
if(e > mid) ans += query(b , e , rson);
return ans;
}
int main()
{
srand(2333666);
int n , m , i , l , r , s , k , x , p , t;
n = read() , m = read();
for(i = 1 ; i <= n ; i ++ ) w[i] = read() , update(i , 1 , 1 , n , root[w[i]]);
while(m -- )
{
l = read() , r = read() , s = read() , k = read() , p = 0;
for(i = 1 ; i <= 15 ; i ++ )
{
t = w[rand() % (r - l + 1) + l];
if(query(l , r , 1 , n , root[t]) > (r - l + 1) >> 1)
{
p = t;
break;
}
}
if(!p) p = s;
printf("%d\n" , p);
for(i = 1 ; i <= k ; i ++ ) x = read() , update(x , -1 , 1 , n , root[w[x]]) , update(x , 1 , 1 , n , root[p]) , w[x] = p;
}
p = -1;
for(i = 1 ; i <= 15 ; i ++ )
{
t = w[rand() % n + 1];
if(a[root[t]].si > n >> 1)
{
p = t;
break;
}
}
printf("%d\n" , p);
return 0;
}
05-11 14:44