分块入门（学习笔记）

分块就是通过比较暴力的方式去处理一些数据结构问题

分块的复杂度分析

分块核心思想就是快速处理整块，暴力处理零散部分

每次处理零散部分之前，要先将零散块的标记清空

练习：

hzwer数列入门九题

bzoj 蒲公英：

询问区间最小众数

预处理区间 l，r 内的最小众数，询问时整块和零散块分别询问，比较一下

注意！！ 写代码的时候要分清楚块的编号和原始编号啊qaq

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<stack>
#include<queue>
using namespace std;
typedef long long ll;
const int maxn = 50010;
int n,m,q,blo;
int a[maxn],b[maxn],c[maxn],bl[maxn],f[1000][1000],g[1000][1000],sum[1000][maxn];
int v[1000][maxn];

void calc(){ int l=1,r=n; while(l<=r) {int mid=(l+r)/2; if(mid*mid*mid<=n) blo=mid,l=mid+1; else r=mid-1; } }

int query(int l,int r){
    int res=0; int mx=0,z=0;
    memset(c,0,sizeof(c));
    for(int i=l;i<=min(r,bl[l]*blo);++i) c[a[i]]++;
    if(bl[l]!=bl[r])
        for(int i=(bl[r]-1)*blo+1;i<=r;++i)
            c[a[i]]++;
    if(bl[r]-1>bl[l])
        for(int j=1;j<=q;++j)
            c[j]+=sum[bl[r]-1][j]-sum[bl[l]][j];
    for(int i=1;i<=q;++i){
        if(c[i]>mx){
            mx=c[i];
            z=i;
        }
    }
    if(mx<g[bl[l]+1][bl[r]-1]){
        z=f[bl[l]+1][bl[r]-1];
    }else if(mx==g[bl[l]+1][bl[r]-1]){
        z=min(z,f[bl[l]+1][bl[r]-1]);
    }
    return z;
}

ll read(){ ll s=0,f=1; char ch=getchar(); while(ch<'0' || ch>'9'){ if(ch=='-') f=-1; ch=getchar(); } while(ch>='0' && ch<='9'){ s=s*10+ch-'0'; ch=getchar(); } return s*f;}
int main(){
    n=read(),m=read(); blo=sqrt(n);
    for(int i=1;i<=n;++i){ a[i]=read(),b[i]=a[i]; bl[i]=(i-1)/blo+1;  }
    sort(b+1,b+1+n);
    
    q=unique(b+1,b+1+n)-b-1;
    for(int i=1;i<=n;++i) a[i]=lower_bound(b+1,b+1+q,a[i])-b;
    
    for(int i=1;i<=bl[n];++i){
        for(int j=1;j<=q;++j){
            sum[i][j]+=sum[i-1][j];
        } 
        for(int k=(i-1)*blo+1;k<=min(i*blo,n);k++){
            ++sum[i][a[k]];
        }
    }
    for(int i=1;i<=bl[n];++i){
        int res,mx;
        memset(c,0,sizeof(c));
        for(int j=i;j<=bl[n];++j){
            res=0,mx=0;
            for(int k=(j-1)*blo+1;k<=min(j*blo,n);++k){
                ++c[a[k]];
            }
            for(int k=1;k<=q;++k)
                if(c[k]>mx){
                    mx=c[k];
                    res=k;
                }
            g[i][j]=mx;
            f[i][j]=res;
        }
    }
    int ans=0;
    int l,r;
    for(int i=1;i<=m;++i){
        l=read(),r=read();
        l=(l+b[ans]-1)%n+1; r=(r+b[ans]-1)%n+1;
        if(l>r) swap(l,r);
        ans=query(l,r);
        printf("%d\n",b[ans]);
    }
    return 0;
}