题解 P3765 【总统选举】
蒟蒻的超长代码
理解到以后 这道题其实就是平衡树和线段树的模板而已
前置技能 p2397 yyy loves Maths VI (mode)
题意是找n个数内出现次数大于n/2的数 保证存在这个数
用的方法叫做摩尔投票法
首先我们注意到这样一个现象： 在任何数组中，出现次数大于该数组长度一半的值只能有一个。
摩尔投票法的基本思想很简单，在每一轮投票过程中，从数组中找出一对不同的元素，将其从数组中删除。
这样不断的删除直到无法再进行投票，如果数组为空，则没有任何元素出现的次数超过该数组长度的一半。如果只存在一种元素，那么这个元素则可能为目标元素。（注意这个可能 这就是这道题代码长度翻一倍的原因
不懂？上代码一看就懂了
int cnt=0,t=0;//t是目前找到的众数
for(int i=1;i<=n;i++)
{
int x;
scanf("%d",&x);
if(cnt==0) t=x,cnt=1;
else
{
if(x!=t) cnt--;
else cnt++;
}
}这样做时间复杂度是线性的 而且连数组都不用开
回到这道题
有了这个前置技能以后 这道题的第一个思路应该很明显了：用线段树维护一个区间的cnt和众数
但是用线段树维护 必须保证维护的东西满足区间可加性
显然摩尔投票法是有区间可加性的
具体来说 如果两个儿子的众数相同 这个节点的众数就等于儿子的众数 cnt就等于两个儿子的cnt相加
如果不同 这个节点的众数就等于cnt较大的那个儿子的众数 cnt就等于大的减去小的
写成代码也很简单
if(tree[ls].num==tree[rs].num) tree[id].num=tree[ls].num,tree[id].cnt=tree[ls].cnt+tree[rs].cnt;
else
{
if(tree[ls].cnt>=tree[rs].cnt) tree[id].cnt=tree[ls].cnt-tree[rs].cnt,tree[id].num=tree[ls].num;
else tree[id].cnt=tree[rs].cnt-tree[ls].cnt,tree[id].num=tree[rs].num;
}那么这道题已经解决了一半了
目前还有一个问题 这道题并不保证有一个元素出现的次数超过区间的一半
也就是说我们费尽千辛万苦找到的众数可能是错的qwq
这里注意 如果有一个元素出现的次数超过区间的一半的话 找到的这个数一定是正确的 但是凡事就怕万一
所以我们需要验证这个数在这个区间内出现的次数是否大于区间的长度除以2
这里用平衡树来维护 其实我也想过线段树 如果点数小的话应该是可以的 但是数据辣么大我还真写不出来
平衡树 动态开点 加上k总共<=10^6点条件 点是能开下的
怎么验证答案呢？
对于每一个人 开一个平衡树 树中存的是所有支持他的人的编号
对于一个区间l,r 我们要求的是编号在l~r之间的支持编号为i的人的数量
那么用平衡树找到编号小于等于r的人中支持i的人的数量 再找到编号小于等于l-1的人 相减就可以了
怎么找呢 因为不存在重复的数 其实就是找一个数的排名啦
所以这道题的主要思路就是这样了
整理一下：
首先预处理 对于每一个人建一棵平衡树 也就是在a[i]这棵平衡树中加入i这个点 表示i这个人支持a[i] 然后建好线段树
然后处理询问 先在线段树中找到区间l,r中可能是众数的那个编号x 然后在平衡树中验证x在区间l,r中出现的次数是否大于(r-l+1) 如果大于 就把s替换成x
然后修改 要修改线段树的叶子节点 在原来i支持的人的那棵平衡树中删去i 在现在i支持的人的平衡树中加上i这个点
最后的处理和中间也是一样的
然后就上代码啦 码量超大 因为打了一棵线段树 一棵平衡树 为了方便 封装了线段树和平衡树 因为喜欢splay打的splay以至于跑的非常慢
要建很多棵树的话 还是封装起来比较方便
个人认为这道题思路如果理清楚了就不算难 但是要有前置知识还要打对两棵树 在考场上还是很有难度
#include<bits/stdc++.h>
#define ls id<<1
#define rs id<<1|1
#define inf 0x7f7f7f7f
using namespace std;
int k,aa[5000010];
struct xd_node
{
int l,r;
int cnt,num;//和找众数那道题一样 维护一个cnt和众数的序号
}tree[5000010];
struct xd_tree
{
void change(int id)
{
if(tree[ls].num==tree[rs].num) tree[id].num=tree[ls].num,tree[id].cnt=tree[ls].cnt+tree[rs].cnt;
else
{
if(tree[ls].cnt>=tree[rs].cnt) tree[id].cnt=tree[ls].cnt-tree[rs].cnt,tree[id].num=tree[ls].num;
else tree[id].cnt=tree[rs].cnt-tree[ls].cnt,tree[id].num=tree[rs].num;
}
}
void build(int id,int l,int r)
{
tree[id].l=l; tree[id].r=r;
if(l==r)
{
tree[id].cnt=1;
tree[id].num=aa[l];
return;
}
int mid=(l+r)>>1;
build(ls,l,mid); build(rs,mid+1,r);
change(id);
}
void updata(int id,int pos,int w)
{
if(tree[id].l==pos&&tree[id].r==pos)
{
tree[id].num=w;
tree[id].cnt=1;
return;
}
int mid=(tree[id].l+tree[id].r)>>1;
if(mid>=pos) updata(ls,pos,w);
else updata(rs,pos,w);
change(id);
}
xd_node search(int id,int l,int r)
{
if(tree[id].l==l&&tree[id].r==r) return tree[id];
int mid=(tree[id].l+tree[id].r)>>1;
if(mid>=r) return search(ls,l,r);
else if(mid<l) return search(rs,l,r);
else
{
xd_node a=search(ls,l,mid),b=search(rs,mid+1,r),c;
if(a.num==b.num) c.num=a.num,c.cnt=a.cnt+b.cnt;
else
{
if(a.cnt>=b.cnt) c.cnt=a.cnt-b.cnt,c.num=a.num;
else c.cnt=b.cnt-a.cnt,c.num=b.num;
}
return c;
}
}
}a;
struct splay_node
{
int fa,ch[2],w,size;
}t[5000010];//splay节点可以公用 节点数要开很大
struct splay_tree
{
int root;
void updata(int x)
{
t[x].size=t[t[x].ch[0]].size+t[t[x].ch[1]].size+1;
}
void rotate(int x)
{
int y=t[x].fa; int z=t[y].fa;
int f=x==t[y].ch[1];
t[z].ch[y==t[z].ch[1]]=x; t[x].fa=z;
t[y].ch[f]=t[x].ch[f^1]; t[t[x].ch[f^1]].fa=y;
t[x].ch[f^1]=y; t[y].fa=x;
updata(y); updata(x);
}
void splay(int x,int goal)
{
while(t[x].fa!=goal)
{
int y=t[x].fa;
int z=t[y].fa;
if(z==goal) rotate(x);
else
{
if((t[z].ch[0]==y)^(t[y].ch[0]==x)) rotate(x);
else rotate(y);
rotate(x);
}
}
if(goal==0) root=x;
}
void find(int x)
{
int id=root; if(!id) return ;
while(t[id].ch[x>t[id].w]&&t[id].w!=x) id=t[id].ch[x>t[id].w];
splay(id,0);
}
int next(int x,int f)
{
find(x); int id=root;
if((t[id].w>x&&f==1)||(t[id].w<x&&f==0)) return id;
id=t[id].ch[f];
while(t[id].ch[f^1]) id=t[id].ch[f^1];
return id;
}
void adde(int x)
{
int id=root,fa=0;
while(id) t[id].size++,fa=id,id=t[id].ch[x>t[id].w];
t[++k].w=x; if(fa) t[fa].ch[x>t[fa].w]=k;
t[k].fa=fa; t[k].size=1; splay(k,0);
}
void del(int x)
{
int qq=next(x,0),hj=next(x,1);
splay(qq,0); splay(hj,qq);
t[hj].ch[0]=0; updata(hj); updata(qq);
}
int get(int x)//找有多少个小于等于x的数 就是找x的排名 因为有个-inf的点 所以-1 又因为ans只加了左子树的大小没有加上x这个数 所以直接返回ans
{
find(x); if(t[root].w!=x) x=t[next(x,0)].w;//如果不存在x这个点 找x的前驱
int id=root,ans=0;
while(1)
{
if(t[id].w>x) id=t[id].ch[0];
else if(t[id].w==x)
{
ans+=t[t[id].ch[0]].size;
splay(id,0);
return ans;
}
else
{
ans+=t[t[id].ch[0]].size+1;
id=t[id].ch[1];
}
}
}
}b[500010];//对每个人建一棵splay 存储支持他的人
int main()
{
int n,m;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) b[i].adde(-inf),b[i].adde(inf);//平衡树初始化
for(int i=1;i<=n;i++) scanf("%d",&aa[i]),b[aa[i]].adde(i);
a.build(1,1,n);//线段树初始化
for(int i=1;i<=m;i++)
{
int l,r,s,q;
scanf("%d%d%d%d",&l,&r,&s,&q);
int x=a.search(1,l,r).num;//x是最有可能是区间众数的人
int sum=b[x].get(r)-b[x].get(l-1);//寻找l~r区间内支持x的人的个数
if(sum>(r-l+1)/2) s=x;//如果这个人数超过了区间的一半
for(int i=1;i<=q;i++)
{
scanf("%d",&x);
a.updata(1,x,s);//把x支持的人变成s
b[aa[x]].del(x); aa[x]=s;
b[aa[x]].adde(x);
}
printf("%d\n",s);
}
int x=a.search(1,1,n).num;
int sum=b[x].get(n);
if(sum>n/2) printf("%d",x);
else printf("-1");
return 0;
}