题解 P3765 【总统选举】
斯德哥尔摩
2018-09-18 00:17:07
[P3765 总统选举](https://www.luogu.org/problemnew/show/P3765)
楼下几位好强啊，两位巨佬都没有给出代码，还有一位巨佬用了$STL$的平衡树，看得我好无奈啊。。。
首先得会这题：[P2397 yyy loves Maths VI (mode)](https://www.luogu.org/problemnew/show/P2397)
直接用对抗法/消去法找到众数即可。
那么，带上修改和多次询问呢？
也就是这题？
我是看这位巨佬的博客弄懂的：[链接](https://blog.csdn.net/Ab_Ever/article/details/72675837)
我们发现上述那个对抗法是可以进行区间合并的。
也就是能从$[l,mid],[mid+1,r]$合并成$[l,r]$。
记录当前的区间众数，区间众数在对抗后出现了多少次。
合并的时候，分两种情况：
1. 当两个区间的区间众数相等时，直接把次数相加。
2. 当两个区间的区间众数不相时，将出现次数多的作为合并后区间的区间众数，出现次数就是$\text{出现次数多的次数-出现次数少的次数}$。
这个合并让我们想起了什么？
或者说我们应该如何维护？
### 线段树！
修改直接单点修改，查询的时候因为维护了两个值：区间众数以及出现次数，直接返回一个结构体就好。
这题就做完了
吗？
并不。
因为“众数”不一定存在！
就是说未必有满足题目的答案，我们维护出的未必是正确答案，只是维护的那个数是“最具有成为‘众数’的潜质”的数罢了。
所以我们需要一个平衡树来检验我们求出的“区间众数”是否是真正的区间众数。
检验很简单，每个人开个$Treap$，判断在$[l,r]$内有几个人选他就行了。
差分一下，就可以在$Treap$上进行普通的二叉查找了。
复杂度是$O(\sum k_i\log_2n)$，可以通过。
附上长长的封装的代码：
```cpp
#include<iostream>
#include<algorithm>
#include<cstdio>
#define MAXN 500010
using namespace std;
int n,m;
int val[MAXN];
inline int read(){
int date=0,w=1;char c=0;
while(c<'0'||c>'9'){if(c=='-')w=-1;c=getchar();}
while(c>='0'&&c<='9'){date=date*10+c-'0';c=getchar();}
return date*w;
}
namespace T{//这是个指针+结构体的裸的Treap，不习惯可以自己写，因为这是纯板子。。。
struct node{
node* son[2];
int v,w,s,flag;
node(){
son[0]=son[1]=NULL;
w=rand();
v=0;
s=flag=1;
}
};
node* root[MAXN];
inline void maintain(node* &u){
u->s=u->flag;
if(u->son[0]!=NULL)u->s+=u->son[0]->s;
if(u->son[1]!=NULL)u->s+=u->son[1]->s;
}
inline void turn(node* &u,int f){
node* t=u->son[f^1];
u->son[f^1]=t->son[f];
t->son[f]=u;
maintain(u);
maintain(t);
u=t;
}
void insert(node* &u,int x){
if(u==NULL){
u=new node;
u->v=x;
return;
}
else if(u->v==x){
u->flag++;
maintain(u);
return;
}
int y=u->v<x?1:0;
insert(u->son[y],x);
if(u->son[y]->w>u->w)turn(u,y^1);
else maintain(u);
}
void remove(node* &u,int x){
if(u==NULL)return;
if(u->v==x){
if(u->flag>1)u->flag--;
else{
if(u->son[0]==NULL&&u->son[1]==NULL)u=NULL;
else if(u->son[0]!=NULL&&u->son[1]!=NULL){
if(u->son[0]->w>u->son[1]->w){
turn(u,1);
remove(u->son[1],x);
}
else{
turn(u,0);
remove(u->son[0],x);
}
}
else{
if(u->son[0]==NULL)u=u->son[1];
else u=u->son[0];
}
}
if(u!=NULL)maintain(u);
}
else{
if(u->v>x)remove(u->son[0],x);
else if(u->v<x)remove(u->son[1],x);
if(u!=NULL)maintain(u);
}
}
int query(node* u,int k){//这个函数是纯的二叉查找
if(u==NULL)return 0;
int lsons=0;
if(u->son[0]!=NULL)lsons=u->son[0]->s;
if(k<u->v)return query(u->son[0],k);
else if(k>=u->v)return lsons+u->flag+query(u->son[1],k);
}
}
namespace ST{//线段树，也是纯板子，不习惯也可以自己写。
#define LSON rt<<1
#define RSON rt<<1|1
#define DATA(x) a[x].data
#define NUM(x) a[x].num
#define LSIDE(x) a[x].l
#define RSIDE(x) a[x].r
struct Segment_Tree{
int data,num,l,r;
}a[MAXN<<2];
inline void pushup(int rt){
if(DATA(LSON)==DATA(RSON)){
DATA(rt)=DATA(LSON);
NUM(rt)=NUM(LSON)+NUM(RSON);
}
else if(NUM(LSON)>NUM(RSON)){
DATA(rt)=DATA(LSON);
NUM(rt)=NUM(LSON)-NUM(RSON);
}
else{
DATA(rt)=DATA(RSON);
NUM(rt)=NUM(RSON)-NUM(LSON);
}
}
void buildtree(int l,int r,int rt){
LSIDE(rt)=l;RSIDE(rt)=r;DATA(rt)=NUM(rt)=0;
if(l==r){
DATA(rt)=val[l];
NUM(rt)=1;
return;
}
int mid=l+r>>1;
buildtree(l,mid,LSON);
buildtree(mid+1,r,RSON);
pushup(rt);
}
void update(int k,int c,int rt){
if(LSIDE(rt)==RSIDE(rt)){
DATA(rt)=c;
NUM(rt)=1;
return;
}
int mid=LSIDE(rt)+RSIDE(rt)>>1;
if(k<=mid)update(k,c,LSON);
else update(k,c,RSON);
pushup(rt);
}
Segment_Tree query(int l,int r,int rt){
if(l<=LSIDE(rt)&&RSIDE(rt)<=r)return a[rt];
int mid=LSIDE(rt)+RSIDE(rt)>>1;
Segment_Tree ans,lson=(Segment_Tree){0,0,0,0},rson=(Segment_Tree){0,0,0,0};
if(l<=mid)lson=query(l,r,LSON);
if(mid<r)rson=query(l,r,RSON);
if(lson.data==rson.data){
ans.data=lson.data;
ans.num=lson.num+rson.num;
}
else if(lson.num>rson.num){
ans.data=lson.data;
ans.num=lson.num-rson.num;
}
else{
ans.data=rson.data;
ans.num=rson.num-lson.num;
}
return ans;
}
}
void work(){
int l,r,s,k,x,ans;
while(m--){
l=read();r=read();s=read();k=read();
ans=ST::query(l,r,1).data;
if((T::query(T::root[ans],r)-T::query(T::root[ans],l-1))<=(r-l+1)/2)ans=s;
//检验答案
printf("%d\n",ans);//求出答案
while(k--){//修改
x=read();
ST::update(x,ans,1);
T::remove(T::root[val[x]],x);
val[x]=ans;
T::insert(T::root[val[x]],x);
}
}
ans=ST::query(1,n,1).data;
if((T::query(T::root[ans],r)-T::query(T::root[ans],l-1))<=n/2)ans=-1;
//检验答案
printf("%d\n",ans);//最后还有一遍。。。
}
void init(){//读入+预处理
srand(2002);//随机种子随便
n=read();m=read();
for(int i=1;i<=n;i++){
val[i]=read();
T::root[i]=NULL;
}
ST::buildtree(1,n,1);
for(int i=1;i<=n;i++)T::insert(T::root[val[i]],i);
}
int main(){//主函数So easy!
init();
work();
return 0;
}
```