数列分块入门 9 link1

数列分块入门 9 link2

代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;namespace sio{void Sr(int &a){a=0;char ch=getchar_unlocked();bool ok=0;while(ch<'0'||ch>'9'){if(ch=='-')ok^=1;ch=getchar_unlocked();}while(ch>='0'&&ch<='9'){a=(a<<1)+(a<<3)+(ch^48);ch=getchar_unlocked();}if(ok)a=-a;}void Sw(int a){if(a==0){putchar_unlocked('0');return;}if(a<0){putchar('-');Sw(-a);return;}char ch[20];int till=0;while(a){ch[till++]=a%10;a/=10;}while(till)putchar_unlocked(ch[--till]^48);}struct Srr{Srr operator>>(int &a){Sr(a);return {};}Srr operator>>(char &ch){ch=getchar_unlocked();while(ch==' '||ch=='\n'){ch=getchar_unlocked();}return {};}}in;struct Sww{Sww operator<<(const int a){Sw(a);return {};}Sww operator<<(const char ch){putchar_unlocked(ch);return {};}Sww operator <<(const string s){for(int i=0;i<s.size();i++){putchar_unlocked(s[i]);}return {};}}out;}using namespace sio;
int a[100005],b[100005],sum[335][100005],len,id[100005],n;int top=0,t;//sum:1～i块内j
int y[100005],ansid[335][335],ansv[335][335];
void init(){
    for(int i=0;i<t;i++){
        if(i!=0){for(int j=0;j<=top;j++){sum[i][j]=sum[i-1][j];}}
        for(int j=i*len;id[j]==i;j++){sum[i][a[j]]++;}
    }
    for(int l=0;l<t;l++){
        int idd=0,minn=-1;
        memset(y,0,sizeof(y));
        for(int r=l;r<n;r++){//[l,r]
            for(int i=r*len;id[i]==r;i++){
                y[a[i]]++;
                if(y[a[i]]>minn||(y[a[i]]==minn&&a[idd]>a[i]))minn=y[a[i]],idd=i;
            }
            ansid[l][r]=idd;
            ansv[l][r]=minn;
        }
    }
}
bool vis[100005];
int cha(int l,int r){
    int q=id[l],w=id[r];
    memset(y,0,sizeof(y));int idd=0,minn=-1;
    if(w-q<=1){
        for(int i=l;i<r;i++){
            if((++y[a[i]])>minn||(y[a[i]]==minn&&a[idd]>a[i]))minn=y[a[i]],idd=i;
        }
        //cout<<idd<<"\n";
        return b[idd];
    }
    idd=ansid[q+1][w-1];
    minn=ansv[q+1][w-1];
    memset(vis,0,sizeof(vis));
    for(int i=l;id[i]==q;i++){
        ++y[a[i]];
        if(!vis[a[i]]){
            vis[a[i]]=1;
            for(int i=q+1;i<w;i++){
                y[a[i]]+=sum[i][a[i]];
            }
        }
        if((y[a[i]])>minn||(y[a[i]]==minn&&a[idd]>a[i]))minn=y[a[i]],idd=i;
    }
    for(int i=r;i==w;i--){
        ++y[a[i]];
        if(!vis[a[i]]){
            vis[a[i]]=1;
            y[a[i]]+=sum[w-1][a[i]]-sum[q+1][a[i]];
        }
        if((y[a[i]])>minn||(y[a[i]]==minn&&a[idd]>a[i]))minn=y[a[i]],idd=i;
    }
       // cout<<idd<<"\n";
    return b[idd];
}

signed main(){
    in>>n;
    len=sqrt(n);
    t=n/len+min(1LL,n%len);
    for(int i=0;i<n;i++){
        in>>a[i];
        b[i]=a[i];
        id[i]=i/len;
    }
    sort(b,b+n);
    a[0]=0;
    for(int i=1;i<n;i++){
        if(b[i]!=b[i-1]){
            a[i]=++top;
           // mp19937[top]=a[i];
        }else{
            a[i]=a[i-1];
        }
    }
    init();
    int m=n;
    for(;m--;){
        int l,r;
        in>>l>>r;
        out<<cha(--l,--r)<<"\n";
    }
    return 0;
}

虽然我也知道这种代码没人调。。。