求助分块题（有注释，会关注滴）

漠寒 @ 2021-07-16 21:47:44

#include<bits/stdc++.h>
using namespace std;
#define re register
inline void read(int &res){
    res=0;
    int f=1;
    char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9')res=(res<<1)+(res<<3)+c-48,c=getchar();
    res*=f;
}
int n,m;
int l,r;
int tot;
int flag[500005];
map<int,int>vis;
int fk[500005];
int cs[500005];
int f[800][800];
int s[800][800];
int bak[500005];
int fr[500005];
int num[500005];
int pos[500005];
int mx;
int ks;
int cnt[600015];
vector<int>v[500005];
bool isf[500005],isb[500005];
int las;
int sqr;
signed main()
{
    freopen("ynoi.in", "r", stdin);
    read(n);read(m);
    sqr=sqrt(n);
    for(re int i=1;i<=n;i++){
        fk[i]=i/sqr+1;
        if(fk[i]>fk[i-1]){//块的分界线 
            bak[ks++]=i-1;//上一块的末位置 
            fr[ks]=i;//该块开头位置 
            isb[i-1]=isf[i]=1;//标记是否为起点和终点 
        }
    }
    bak[ks]=n;
    isb[n]=1;
    for(re int i=1;i<=n;i++){
        read(cs[i]);
        if(!vis[cs[i]]){
            vis[cs[i]]=++tot;//数值的标记 
            num[tot]=cs[i];//该类对应数值 
        }
        flag[i]=vis[cs[i]];//属于哪一类 
        v[flag[i]].push_back(i);
        pos[i]=v[flag[i]].size()-1;//该类型中其位置 
    }
    for(re int i=1;i<=ks;i++){
        int k=fr[i]-1;
        mx=0;
        memset(cnt,0,sizeof(cnt));
        for(re int j=i;j<=ks;j++){//第i块到第j块一共的情况 
            s[i][j]=s[i][j-1];
            while(k<bak[j]){
                ++k;
                cnt[flag[k]]++;
                if(cnt[flag[k]]>mx||(cnt[flag[k]]==mx&&cs[k]<num[s[i][j]])){
                    mx=cnt[flag[k]];
                    s[i][j]=flag[k];//众数是哪一类 
                }
            }
            f[i][j]=mx;//众数的个数 
        }
    }
    while(m--){
        read(l);read(r);
        l=(l+las-1)%n+1,r=(r+las-1)%n+1;
        if(l>r)swap(l,r);
        int ll=fk[l]+(isf[l]?0:1),rr=fk[r]-(isb[r]?0:1);
        //cout<<ll<<" "<<rr<<endl;
        if(ll>rr){//在同一块内 
            mx=0;
            memset(cnt,0,4*(tot+20));
            for(int i=l;i<=r;i++){
                cnt[flag[i]]++;
                if(cnt[flag[i]]>mx||cnt[flag[i]]==mx&&cs[i]<num[las]){
                    mx=cnt[flag[i]];
                    las=flag[i];
                }
            }
        }
        else {//不同块，区间内部有完整块 
            mx=f[ll][rr];
            las=s[ll][rr];
            //cout<<mx<<" "<<las<<endl;
            int kl=fr[ll],kr=bak[rr];
            while(kl>l){
                int s=flag[--kl];
                if(pos[kl]+mx>=v[s].size())continue;
                if(v[s][pos[kl]+mx]<=kr||v[s][pos[kl]+mx-1]<=kr&&cs[kl]<num[las]){//往后找mx个仍在范围内 
                    mx++;
                    las=s;
                }
            }
            while(kr<r){
                int s=flag[++kr];
                if(pos[kl]<mx)continue;
                if(v[s][pos[kl]-mx]>=kl||v[s][pos[kl]-mx+1]>=kl&&cs[kr]<num[las]){//往前找mx个仍在范围内 
                    mx++;
                    las=s;
                }
            }
        }
        printf("%d\n",las=num[las]);
    }
    return 0;
}

by Liuyuzhuo @ 2021-07-16 22:33:14

随便调了下，明天再看

#include<bits/stdc++.h>
using namespace std;
#define re register
inline void read(int &res)
{
    res=0;
    int f=1;
    char c=getchar();
    while(c<'0'||c>'9')
    {
        if(c=='-')f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9')res=(res<<1)+(res<<3)+c-48,c=getchar();
    res*=f;
}
int n,m;
int l,r;
int tot;
int flag[500005];
map<int,int>vis;
int fk[500005];
int cs[500005];
int f[800][800];
int s[800][800];
int bak[500005];
int fr[500005];
int num[500005];
int pos[500005];
int mx;
int ks;
int cnt[600015];
vector<int>v[500005];
bool isf[500005],isb[500005];
int las;
int sqr;
signed main()
{
    read(n);
    read(m);
    sqr=sqrt(n);
    for(re int i=1; i<=n; i++)
    {
        fk[i]=i/sqr+1;
        if(fk[i]>fk[i-1]) //块的分界线
        {
            bak[ks++]=i-1;//上一块的末位置
            fr[ks]=i;//该块开头位置
            isb[i-1]=isf[i]=1;//标记是否为起点和终点
        }
    }
    bak[ks]=n;
    isb[n]=1;
    for(re int i=1; i<=n; i++)
    {
        read(cs[i]);
        if(!vis[cs[i]])
        {
            vis[cs[i]]=++tot;//数值的标记
            num[tot]=cs[i];//该类对应数值
        }
        flag[i]=vis[cs[i]];//属于哪一类
        v[flag[i]].push_back(i);
        pos[i]=v[flag[i]].size()-1;//该类型中其位置
    }
    for(re int i=1; i<=ks; i++)
    {
        int k=fr[i]-1;
        mx=0;
        memset(cnt,0,sizeof(cnt));
        for(re int j=i; j<=ks; j++) //第i块到第j块一共的情况
        {
            s[i][j]=s[i][j-1];
            while(k<bak[j])
            {
                ++k;
                cnt[flag[k]]++;
                if(cnt[flag[k]]>mx||(cnt[flag[k]]==mx&&cs[k]<num[s[i][j]]))
                {
                    mx=cnt[flag[k]];
                    s[i][j]=flag[k];//众数是哪一类
                }
            }
            f[i][j]=mx;//众数的个数
        }
    }
    while(m--)
    {
        read(l);
        read(r);
        l=(l+las-1)%n+1,r=(r+las-1)%n+1;
        if(l>r)swap(l,r);
        int ll=fk[l]+(isf[l]?0:1),rr=fk[r]-(isb[r]?0:1);
        if(ll>rr) //在同一块内
        {
            mx=0;
            memset(cnt,0,4*(tot+20));
            for(int i=l; i<=r; i++)
            {
                cnt[flag[i]]++;
                if(cnt[flag[i]]>mx||cnt[flag[i]]==mx&&cs[i]<num[las])
                {
                    mx=cnt[flag[i]];
                    las=flag[i];
                }
            }
        }
        else  //不同块，区间内部有完整块
        {
            mx=f[ll][rr];
            las=s[ll][rr];
            //cout<<mx<<" "<<las<<endl;
            int kl=fr[ll],kr=bak[rr];
            while(kl>l)
            {
                int s=flag[--kl];
                if(pos[kl]+mx>=v[s].size())continue;
                if(v[s][pos[kl]+mx]<=r)
                {
                    mx++;
                    las=s;
                }
                else if(v[s][pos[kl]+mx-1]<=kr&&cs[kl]<num[las])
                    las=s;
            }
            while(kr<r)
            {
                int s=flag[++kr];
                if(pos[kr]<mx)continue;
                if(v[s][pos[kr]-mx]>=l)
                {
                    ++mx;
                    las=s;
                }
                else if(v[s][pos[kr]-mx+1]>=l&&cs[kr]<num[las])//往前找mx个仍在范围内
                    las=s;
            }
        }
        printf("%d\n",las=num[las]);
    }
    return 0;
}

by 漠寒 @ 2021-07-17 07:29:44

@字如其人 天哪，我太菜了

by 漠寒 @ 2021-07-17 07:30:13

@Liuyuzhuo OK，谢谢小哥