luogu#P3765. 总统选举

    ID: 7793 远端评测题 1000~5000ms 125MiB 尝试: 2 已通过: 0 难度: 6 上传者: 标签>线段树平衡树洛谷原创O2优化枚举暴力众数构造洛谷月赛

总统选举

题目背景

黑恶势力的反攻计划被小 C 成功摧毁,黑恶势力只好投降。秋之国的人民解放了,举国欢庆。此时,原秋之国总统因没能守护好国土,申请辞职,并请秋之国人民的大救星小 C 钦定下一任。

作为一名民主人士,小 C 决定举行全民大选来决定下一任。为了使最后成为总统的人得到绝大多数人认同,小 C 认为,一个人必须获得超过全部人总数的一半的票数才能成为总统。如果不存在符合条件的候选人,小 C 只好自己来当临时大总统。为了尽可能避免这种情况,小 C 决定先进行几次小规模预选,根据预选的情况,选民可以重新决定自己选票的去向。

由于秋之国人数较多,统计投票结果和选票变更也成为了麻烦的事情,小 C 找到了你,让你帮他解决这个问题。

题目描述

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

共有 mm 次预选,每次选取编号 [li,ri][l_i,r_i] 内的选民展开小规模预选,在该区间内获得超过区间大小一半的票的人获胜。如果没有人获胜,则由小 C 钦定一位候选者获得此次预选的胜利(获胜者可以不在该区间内),每次预选的结果需要公布出来,并且每次会有 kik_i 个人决定将票改投向该次预选的获胜者。

全部预选结束后,公布最后成为总统的候选人。

输入格式

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

第二行 nn 个整数,分别表示编号 1n1 \sim n 的选民投的票。

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

输出格式

m+1m+1 行,前 mm 行表示各次预选的结果,最后一行表示最后成为总统的候选人,若最后仍无人胜选,输出 1-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%20 \% 的数据,1n,m50001 \leq n,m \leq 5000

对于前 40%40 \% 的数据,1n,m500001 \leq n,m \leq 50000ki50000\sum k_i \leq 50000

对于前 50%50 \% 的数据,1n,m1051 \leq n,m \leq {10}^5ki2×105\sum k_i \leq 2 \times {10}^5

对于数据点 6~7,保证所有选票始终在 1101 \sim 10 之间。

对于 100%100 \% 的数据,1n,m5×1051 \leq n,m \leq 5 \times {10}^5ki106\sum k_i \leq 10^61lirin1 \leq l_i \leq r_i \leq n1sin1 \leq s_i \leq n