CF840D Destiny 题解

· · 题解

分析

为什么要随机化。

考虑莫队。

对于询问 i 的一个可行数 x，其条件为：cnt_x > \frac{r_i-l_i+1}{k_i}。我们可以求出来第一个比 \frac{r_i-l_i+1}{k_i} 大的整数 s，就有 cnt_x \ge s。

然后就是一个蓝题。求区间出现次数不小于 s 的最小整数。记录 Cnt_x 表示 x 在区间中的出现次数，cnt_x 表示出现次数为 x 的最小整数。如果用回滚莫队，Cnt_x 大小为不减的，所以在每次 Cnt_x 增加 1 之后都更新一下 cnt_{Cnt_x} 就能保证 x 这个数在 cnt_1 \sim cnt_{Cnt_x} 都有更新。第 i 个询问的答案很显然就是 cnt_{s_i}。

复杂度 O(n \sqrt{n})，不用随机化。

代码

#include<bits/stdc++.h>
using namespace std;
#define re register
#define il inline
#define pii pair<int,int>
#define x first
#define y second
#define gc getchar()
#define rd read()
#define debug() puts("------------")

namespace yzqwq{
    il int read(){
        int x=0,f=1;char ch=gc;
        while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=gc;}
        while(ch>='0'&&ch<='9') x=(x<<1)+(x<<3)+(ch^48),ch=gc;
        return x*f;
    }
    il int qmi(int a,int b,int p){
        int ans=1;
        while(b){
            if(b&1) ans=ans*a%p;
            a=a*a%p,b>>=1;
        }
        return ans;
    }
    il auto max(auto a,auto b){return (a>b?a:b);}
    il auto min(auto a,auto b){return (a<b?a:b);}
    il int gcd(int a,int b){
        if(!b) return a;
        return gcd(b,a%b);
    }
    il int lcm(int a,int b){
        return a/gcd(a,b)*b;
    }
    il void exgcd(int a,int b,int &x,int &y){
        if(!b) return x=1,y=0,void(0);
        exgcd(b,a%b,x,y);
        int t=x;
        x=y,y=t-a/b*x;
        return ;
    }
    mt19937 rnd(time(0));
}
using namespace yzqwq;

const int N=1e6+10,inf=1e8;
int n,m,a[N];
int len,ans[N];
struct node{
    int l,r,k,id;
    il bool operator <(const node &b)const{
        if((l-1)/len!=(b.l-1)/len) return l<b.l;
        return r<b.r;
    }
}q[N];
int cnt1[N],cnt2[N];//大于等于i的最小数
int Cnt1[N],Cnt2[N];//数的出现次数
int del1[N],vis1[N],del2[N],vis2[N],idx1,idx2;

il int get(int x){
    return (x-1)/len+1;
}

il void solve(){
    n=rd,m=rd,len=sqrt(n);
    for(re int i=1;i<=n;++i) a[i]=rd;
    for(re int i=1;i<=m;++i){
        int l=rd,r=rd,s=rd,k;
        k=(r-l+1-1)/s+1;
        if(k==(double)((r-l+1)*1.0/s)) ++k;
        q[i]={l,r,k,i};
    }
    int l=1,r=0,lbk=0;
    sort(q+1,q+m+1);
    for(re int i=0;i<N;++i) ans[i]=inf,cnt1[i]=cnt2[i]=inf,Cnt1[i]=Cnt2[i]=0,vis1[i]=vis2[i]=0;
    idx1=idx2=0;
    for(re int i=1;i<=m;++i){
        int bl=get(q[i].l),br=get(q[i].r);
        if(bl==br){
            for(re int j=q[i].l;j<=q[i].r;++j)
                ++Cnt2[a[j]],cnt2[Cnt2[a[j]]]=cnt2[Cnt2[a[j]]]>a[j]?a[j]:cnt2[Cnt2[a[j]]];
            ans[q[i].id]=cnt2[q[i].k];
            for(re int j=q[i].l;j<=q[i].r;++j)
                cnt2[Cnt2[a[j]]]=inf,--Cnt2[a[j]];
            continue;           
        }
        if(bl!=lbk){
            for(re int j=1;j<=idx1;++j) vis1[del1[j]]=0,cnt1[del1[j]]=inf;
            for(re int j=1;j<=idx2;++j) vis2[del2[j]]=0,Cnt1[del2[j]]=0;
            idx1=idx2=0;
            l=min(n,bl*len)+1,r=min(n,bl*len);
            lbk=bl;
        }
        while(r<q[i].r){
            ++r;
            ++Cnt1[a[r]];
            if(!vis1[Cnt1[a[r]]]) vis1[Cnt1[a[r]]]=1,del1[++idx1]=Cnt1[a[r]];
            if(!vis2[a[r]]) vis2[a[r]]=1,del2[++idx2]=a[r];
            cnt1[Cnt1[a[r]]]=cnt1[Cnt1[a[r]]]>a[r]?a[r]:cnt1[Cnt1[a[r]]];
        }
        int l_=l;
        while(l_>q[i].l){
            --l_;
            ++Cnt2[a[l_]];
            cnt2[Cnt1[a[l_]]+Cnt2[a[l_]]]=cnt2[Cnt1[a[l_]]+Cnt2[a[l_]]]>a[l_]?a[l_]:cnt2[Cnt1[a[l_]]+Cnt2[a[l_]]];
        }
        ans[q[i].id]=min(cnt1[q[i].k],cnt2[q[i].k]);
        while(l_<l){
            cnt2[Cnt1[a[l_]]+Cnt2[a[l_]]]=inf;
            --Cnt2[a[l_]],++l_;     
        }
    }
    for(re int i=1;i<=m;++i)
        if(ans[i]<inf) printf("%d\n",ans[i]);
        else printf("-1\n");
    return ;
}

signed main(){
//  freopen(".in","r",stdin);
//  freopen(".out","w",stdout);
    int t=1;while(t--)
    solve();
    return 0;
}