【洛谷P3765】总统选举 | Mrsrz's blog

随机化，平衡树

题目大意：

给定一个数列 $a_{1\sim n}$。

每次询问时，给出 $l,r,s,k$ 以及 $k$ 个不同的数 $b_{1\sim k}$。要求找到 $a_{l\sim r}$ 中出现次数超过一半的那个数（如果不存在，就钦定为 $s$），输出这个数，并把 $a_{b_{1\sim k}}$ 都改为这个数。

最后再询问一遍出现次数超过一半的数。

题解：

如果存在这样一个出现次数超过一半的数，我们每次随机选择一个位置，其为答案的概率大于 $\frac 1 2$。

我们随机 $p$ 次，那么能够找到答案的概率就至少为 $1-\frac{1}{2^p}$，这个概率在回答单个询问时，当 $p$ 在 $15$ 左右时看起来就可以接受了，再说有相当一部分概率是不存在答案的。为了保证稳妥，$p$ 还是尽量开大点。因为当 $p$ 取 $15$ 的时候，最坏情况下全部正确的概率只有不到 $1\%$（用python算出来的），而我取 $p=25$，其正确率就高达 $98.5\%$，几乎不可能出错。

那么我们就需要 check 一个答案是否在区间内出现了超过一半。

我们只需要知道它在区间内的出现次数就可以了。用平衡树查询即可（听说动态开点线段树会被卡空间）。

显然平衡树就可以支持修改了。

那么时间复杂度就是 $O(p(n+m)\log n)$，$p$ 为选定的常数。

我写了替罪羊树，作为练习。这货跑得还挺快？

听说随机算法会被卡常？

Code：

#include<cstdio>
#include<cctype>
#include<vector>
#include<ctime>
#include<cstdlib>
using namespace std;
const int N=5e5+5,M=N*5;
const double alpha=.78;
inline int readint(){
    int c=getchar(),d=0;
    for(;!isdigit(c);c=getchar());
    for(;isdigit(c);c=getchar())d=d*10+(c^'0');
    return d;
}
int n,m,a[N],rt[N];
int pool[M],topL;
int sz[M],ls[M],rs[M],val[M],fa[M];bool tag[M];
vector<int>vec[N];
int sta[N],top;
inline int newnode(int v=0){
    const int ret=pool[topL--];
    sz[ret]=1,tag[ret]=1;
    ls[ret]=rs[ret]=fa[ret]=0;
    val[ret]=v;
    return ret;
}
inline void update(int x){
    sz[x]=sz[ls[x]]+sz[rs[x]]+tag[x];
}
int build(int l,int r){
    if(l>r)return 0;
    const int mid=l+r>>1;
    int ret=newnode(sta[mid]);
    const int ld=build(l,mid-1),rd=build(mid+1,r);
    if(ld)fa[ld]=ret,ls[ret]=ld;
    if(rd)fa[rd]=ret,rs[ret]=rd;
    update(ret);
    return ret;
}
void init(int id){
    top=0;
    for(int i=0;i<vec[id].size();++i)
        sta[++top]=vec[id][i];
    rt[id]=build(1,top);
}
int query(int x,int k){
    int ret=0;
    while(x){
        if(val[x]<k)ret+=sz[ls[x]]+tag[x],x=rs[x];else
            if(val[x]==k)return ret+sz[ls[x]]+tag[x];else x=ls[x];
    }
    return ret;
}
int insert_(int&x,int v,int f){
    int r=0;
    if(!x)x=newnode(v),fa[x]=f;else{
        if(val[x]==v)tag[x]=1;else
        if(val[x]>v)r=insert_(ls[x],v,x);else r=insert_(rs[x],v,x);
        if(sz[x]*alpha<sz[ls[x]]||sz[x]*alpha<sz[rs[x]])r=x;
        update(x);
    }
    return r;
}
void get(int x){
    if(!x)return;
    get(ls[x]);
    if(tag[x])sta[++top]=val[x];
    pool[++topL]=x;
    get(rs[x]);
}
void insert(int&x,int v){
    int id=insert_(x,v,0);
    if(id){
        int isr=rs[fa[id]]==id,f=fa[id];
        top=fa[id]=0;
        get(id);
        id=build(1,top);
        if(!f)x=id;else{
            if(id)fa[id]=f;
            if(isr)rs[f]=id;else ls[f]=id;
            update(f);
        }
    }
}
void erase(int x,int v){
    while(x){
        --sz[x];
        if(val[x]==v){tag[x]=0;return;}
        if(val[x]<v)x=rs[x];else x=ls[x];
    }
    exit(1);
}
int ask(int id,int l,int r){
    return query(id,r)-(l>1?query(id,l-1):0);
}
int main(){
    srand(time(0));
    for(register int i=1;i<M;++i)pool[i]=i;
    topL=M-1;
    n=readint(),m=readint();
    for(int i=1;i<=n;++i)
        vec[a[i]=readint()].push_back(i);
    for(int i=1;i<=n;++i)
        init(i);
    while(m--){
        int l=readint(),r=readint(),s=readint(),k=readint();
        for(int T=1;T<=25;++T){
            int x=a[rand()%(r-l+1)+l];
            int t=ask(rt[x],l,r);
            if(r-l+1<t*2){s=x;break;}
        }
        printf("%d\n",s);
        while(k--){
            int x=readint();
            erase(rt[a[x]],x),insert(rt[a[x]=s],x);
        }
    }
    static int tot[N];
    for(int i=1;i<=n;++i)++tot[a[i]];
    for(int i=1;i<=n;++i)
        if(2*tot[i]>n)return printf("%d\n",i),0;
    puts("-1");
    return 0;
}