P3765 总统选举
题目背景
黑恶势力的反攻计划被小 C 成功摧毁, 黑恶势力只好投降. 秋之国的人民解放了, 举国欢庆. 此时, 原秋之国总统因没能守护好国土, 申请辞职, 并请秋之国人民的大救星小 C 钦定下一任. 作为一名民主人士, 小 C 决定举行全民大选来决定下一任. 为了使最后成为总统的人得到绝大多数人认同, 小 C 认为, 一个人必须获得超过全部人总数的一半的票数才能成为总统. 如果不存在符合条件的候选人, 小 C 只好自己来当临时大总统. 为了尽可能避免这种情况, 小 C 决定先进行几次小规模预选, 根据预选的情况, 选民可以重新决定自己选票的去向. 由于秋之国人数较多, 统计投票结果和选票变更也成为了麻烦的事情, 小 C 找到了你, 让你帮他解决这个问题.
题目描述
秋之国共有 \(n\)个人, 分别编号为 \(1,2,...,n\), 一开始每个人都投了一票, 范围 \(1\)~\(n\), 表示支持对应编号的人当总统. 共有 \(m\)次预选, 每次选取编号 \([l_i,r_i]\)内的选民展开小规模预选, 在该区间内获得超过区间大小一半的票的人获胜, 如果没有人获胜, 则由小 C 钦定一位候选者获得此次预选的胜利 (获胜者可以不在该区间内), 每次预选的结果需要公布出来, 并且每次会有 \(k_i\) 个人决定将票改投向该次预选的获胜者. 全部预选结束后, 公布最后成为总统的候选人.
输入输出格式
输入格式:
第一行两个整数 \(n,m\), 表示秋之国人数和预选次数.
第二行 \(n\)个整数, 分别表示编号 \(1\)~\(n\)的选民投的票.
接下来 \(m\)行, 每行先有 \(4\)个整数, 分别表示 \(l_i,r_i,s_i,k_i\),\(s_i\)表示若此次预选无人胜选, 视作编号为 \(s_i\)的人获得胜利, 接下来 \(k_i\)个整数, 分别表示决定改投的选民.
输出格式:
共 \(m+1\)行, 前 \(m\)行表示各次预选的结果, 最后一行表示最后成为总统的候选人, 若最后仍无人胜选, 输出 \(-1\).
说明
对于前 \(20\%\)的数据,\(1 \leq n,m \leq 5000\).
对于前 \(40\%\)的数据,\(1 \leq n,m \leq 50000\),\(\sum k_i \leq 50000\).
对于前 \(50\%\)的数据,\(1 \leq n,m \leq 100000\),\(\sum k_i \leq 200000\).
对于数据点 \(6\)~\(7\), 保证所有选票始终在 \(1\)~\(10\)之间.
对于 \(100\%\)的数据,\(1 \leq n,m \leq 500,000\),\(\sum k_i \leq 10^6\),\(1 \leq l_i \leq r_i \leq n\),\(1 \leq s_i \leq n\).
好题啊
区间求众数一般情况下只能用分块之类的求解
但是这题当选有条件啊, 大于区间一半哎, 肯定想办法在这里下手
bzoj 有道题叫 made https://www.lydsy.com/JudgeOnline/problem.php?id=2456 , 可以从这里得到启发
这题是这么做的呢
具体的说, 我们从左向右扫描, 假设当前可能成为答案的为 \(v\), 且它出现了 \(cnt\)次, 如果当前数等于 \(x\), 则 \(++cnt\), 否则 \(--cnt\), 若 \(cnt==0\), 则替换 \(x\)为当前数,\(cnt=1\)
这是什么原理呢? 可以理解为减小了整个区间的抵消, 因为要求出现一半以上, 所以当一对不一样的数出现时, 可以把这一对删掉, 减小区间规模
可以这样做得到的数不一定是出现超过一半的, 只是它最有可能
我们可以拿线段树模拟这个区间合并的过程, 维护 \(v\)和 \(cnt\), 直接区间查询, 单点修改
如何检验是否出现超过一半呢? 对每一个候选人, 我们搞一颗平衡树维护, 以位置为 BST 性质, 这样直接把区间分离出来看看大小就行了
- Code:
- #include <cstdio>
- #include <cstdlib>
- #define ls ch[now][0]
- #define rs ch[now][1]
- const int N=2e6+10;
- int bvote[N<<2],cnt[N<<2],vote[N],n,m;
- void updata(int id)
- {
- if(bvote[id<<1]==bvote[id<<1|1])
- {
- cnt[id]=cnt[id<<1]+cnt[id<<1|1];
- bvote[id]=bvote[id<<1];
- return;
- }
- if(cnt[id<<1]>cnt[id<<1|1])
- {
- cnt[id]=cnt[id<<1]-cnt[id<<1|1];
- bvote[id]=bvote[id<<1];
- }
- else
- {
- cnt[id]=cnt[id<<1|1]-cnt[id<<1];
- bvote[id]=bvote[id<<1|1];
- }
- }
- void change(int id,int l,int r,int pos,int v)
- {
- if(l==r)
- {
- bvote[id]=v;
- return;
- }
- int mid=l+r>>1;
- if(pos<=mid) change(id<<1,l,mid,pos,v);
- else change(id<<1|1,mid+1,r,pos,v);
- updata(id);
- }
- int query(int id,int l,int r,int L,int R,int &ct)
- {
- if(l==L&&r==R)
- {
- ct=cnt[id];
- return bvote[id];
- }
- int Mid=L+R>>1;
- if(r<=Mid) return query(id<<1,l,r,L,Mid,ct);
- else if(l>Mid) return query(id<<1|1,l,r,Mid+1,R,ct);
- else
- {
- int lv,rv,lc,rc,nv;
- lv=query(id<<1,l,Mid,L,Mid,lc),rv=query(id<<1|1,Mid+1,r,Mid+1,R,rc);
- if(lv==rv) {ct=lc+rc;return lv;}
- if(lc>rc) nv=lv,ct=lc-rc;
- else nv=rv,ct=rc-lc;
- return nv;
- }
- }
- void build(int id,int l,int r)
- {
- if(l==r)
- {
- cnt[id]=1,bvote[id]=vote[l];
- return;
- }
- int mid=l+r>>1;
- build(id<<1,l,mid),build(id<<1|1,mid+1,r);
- updata(id);
- }
- int ch[N][2],siz[N],val[N],dat[N],tot,root[N];
- void updata2(int now){siz[now]=siz[ls]+siz[rs]+1;}
- void split(int now,int k,int &x,int &y)
- {
- if(!now){x=y=0;return;}
- if(dat[now]<=k)
- x=now,split(rs,k,rs,y);
- else
- y=now,split(ls,k,x,ls);
- updata2(now);
- }
- int Merge(int x,int y)
- {
- if(!x||!y) return x+y;
- if(val[x]<val[y])
- {
- ch[x][1]=Merge(ch[x][1],y);
- updata2(x);
- return x;
- }
- else
- {
- ch[y][0]=Merge(x,ch[y][0]);
- updata2(y);
- return y;
- }
- }
- int New(int k)
- {
- val[++tot]=rand(),siz[tot]=1,dat[tot]=k;
- return tot;
- }
- void Insert(int id,int k)
- {
- int x,y;
- split(root[id],k,x,y);
- root[id]=Merge(x,Merge(New(k),y));
- }
- void extrack(int id,int k)
- {
- int x,y,z;
- split(root[id],k,x,y);
- split(x,k-1,x,z);
- root[id]=Merge(x,y);
- }
- int ask(int id,int l,int r)
- {
- int x,y,z,s;
- split(root[id],l-1,x,y);
- split(y,r,z,y);
- s=siz[z];
- root[id]=Merge(x,Merge(z,y));
- return s;
- }
- int main()
- {
- scanf("%d%d",&n,&m);
- for(int i=1;i<=n;i++) scanf("%d",vote+i),Insert(vote[i],i);
- build(1,1,n);
- for(int l,r,s,k,p,ct,i=1;i<=m;i++)
- {
- scanf("%d%d%d%d",&l,&r,&s,&k);
- int naive=query(1,l,r,1,n,ct);
- if(ask(naive,l,r)>(r+1-l>>1)) s=naive;
- printf("%d\n",s);
- for(int j=1;j<=k;j++)
- {
- scanf("%d",&p);
- extrack(vote[p],p);
- vote[p]=s;
- Insert(vote[p],p);
- change(1,1,n,p,vote[p]);
- }
- }
- int nai=bvote[1];
- if((ask(nai,1,n)<<1)>n) printf("%d\n",nai);
- else printf("-1\n");
- return 0;
- }
- 2018.9.5
来源: http://www.bubuko.com/infodetail-2755544.html