0pts 全wa 分块 求调 悬赏1关注

Shadow_Lord @ 2023-07-09 19:33:57

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=5e4+10;
const int M=405;
inline int read()
{
    int s=0,w=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9')s=(s<<3)+(s<<1)+(ch^48),ch=getchar();
    return s*w;
}
int s[M][N],vis[N],h[M][N],ans,l0,r0,iid[N],x,num;
int n,m,len,L[N],R[N],belong[N],cntt;
struct node{
    int num,st;
}p[M][M];
struct Node{
    int id,o,af;
}a[N];
inline bool cmp1(Node a,Node b){return a.o<b.o;}
inline bool cmp2(Node a,Node b){return a.id<b.id;}
int f(int l,int r)
{
    memset(vis,0,sizeof(vis));
    if(belong[l]==belong[r])
    {
        int t=0,re=0x3f3f3f3f;
        for(int i=l;i<=r;i++)
        {
            vis[a[i].af]++;
            if(t<vis[a[i].af]||(t==vis[a[i].af]&&re>a[i].af))
            {
                t=vis[a[i].af];
                re=a[i].af;
            }
        }
        return iid[re];
    }
    int t=p[belong[l]+1][belong[r]-1].num,re=p[belong[l]+1][belong[r]-1].st;
    for(int i=l;i<=R[belong[l]];i++)
    {
        if(vis[a[i].af]==0)vis[a[i].af]=vis[a[i].af]+s[belong[r]-1][a[i].af]-s[belong[l]][a[i].af];
        vis[a[i].af]++;
        if(vis[a[i].af]>t||(vis[a[i].af]==t&&re>a[i].af))
        {
            t=vis[a[i].af];
            re=a[i].af;
        }
    }
    for(int i=L[belong[r]];i<=r;i++)
    {
        if(vis[a[i].af]==0)vis[a[i].af]=vis[a[i].af]+s[belong[r]-1][a[i].af]-s[belong[l]][a[i].af];
        vis[a[i].af]++;
        if(vis[a[i].af]>t||(vis[a[i].af]==t&&re>a[i].af))
        {
            t=vis[a[i].af];
            re=a[i].af;
        }
    }
    return iid[re];
}
signed main()
{   
    n=read();m=read();
    len=sqrt(n);num=n/len;if(n%len)num++;
    memset(L,0x3f3f3f3f,sizeof(L));
    for(int i=1;i<=n;i++)
    {
        a[i].o=read();a[i].id=i;
        belong[i]=(i-1)/len+1;
        L[belong[i]]=min(L[belong[i]],i);
        R[belong[i]]=max(R[belong[i]],i);
    }
    sort(a+1,a+n+1,cmp1);
    for(int i=1;i<=n;i++)
    {
        a[i].af=a[i-1].af;
        if(a[i].o!=a[i-1].o)a[i].af++,cntt++;
        iid[a[i].af]=a[i].o;
        h[belong[a[i].id]][a[i].af]++;
    }
    sort(a+1,a+n+1,cmp2);
    for(int i=1;i<=cntt;i++)
    {
        for(int j=1;j<=num;j++)
        {
            s[j][i]=s[j-1][i]+h[j][i];
        }
    }
    for(int i=1;i<=num;i++)
    {
        memset(vis,0,sizeof(vis));
        for(int j=i;j<=num;j++)
        {
            int kk=0,kt=0;
            for(int k=L[j];k<=R[j];k++)
            {
                vis[a[k].af]++;
                if(vis[a[k].af]>kk)
                {
                    kk=vis[a[k].af];
                    kt=a[k].af;
                }
            }
            if(kk>vis[p[i][j-1].st]||(kk==vis[p[i][j-1].st]&&kt<p[i][j-1].st))
            {
                p[i][j].num=kk;
                p[i][j].st=kt;
            }
            else
            {
                p[i][j].num=p[i][j-1].num;
                p[i][j].st=p[i][j-1].st;
            }
        }
    }
    while(m--)
    {
        l0=read();r0=read();
        int l=((l0+x-1)%n)+1,r=((r0+x-1)%n)+1;
        if(l>r)swap(l,r);
        x=f(l,r);
        cout<<l<<" "<<r<<" ";
        cout<<x<<"\n";
    }
    return 0;
}

by Shadow_Lord @ 2023-07-09 19:53:01

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=5e4+10;
const int M=405;
inline int read()
{
    int s=0,w=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9')s=(s<<3)+(s<<1)+(ch^48),ch=getchar();
    return s*w;
}
int s[M][N],vis[N],h[M][N],ans,l0,r0,iid[N],x,num;
int n,m,len,L[N],R[N],belong[N],cntt;
struct node{
    int num,st;
}p[M][M];
struct Node{
    int id,o,af;
}a[N];
inline bool cmp1(Node a,Node b){return a.o<b.o;}
inline bool cmp2(Node a,Node b){return a.id<b.id;}
int f(int l,int r)
{
    memset(vis,0,sizeof(vis));
    if(belong[l]==belong[r])
    {
        int t=0,re=0x3f3f3f3f;
        for(int i=l;i<=r;i++)
        {
            vis[a[i].af]++;
            if(t<vis[a[i].af]||(t==vis[a[i].af]&&re>a[i].af))
            {
                t=vis[a[i].af];
                re=a[i].af;
            }
        }
        return iid[re];
    }
    int t=p[belong[l]+1][belong[r]-1].num,re=p[belong[l]+1][belong[r]-1].st;
    for(int i=l;i<=R[belong[l]];i++)
    {
        if(vis[a[i].af]==0)vis[a[i].af]=vis[a[i].af]+s[belong[r]-1][a[i].af]-s[belong[l]][a[i].af];
        vis[a[i].af]++;
        if(vis[a[i].af]>t||(vis[a[i].af]==t&&re>a[i].af))
        {
            t=vis[a[i].af];
            re=a[i].af;
        }
    }
    for(int i=L[belong[r]];i<=r;i++)
    {
        if(vis[a[i].af]==0)vis[a[i].af]=vis[a[i].af]+s[belong[r]-1][a[i].af]-s[belong[l]][a[i].af];
        vis[a[i].af]++;
        if(vis[a[i].af]>t||(vis[a[i].af]==t&&re>a[i].af))
        {
            t=vis[a[i].af];
            re=a[i].af;
        }
    }
    return iid[re];
}
signed main()
{   
    n=read();m=read();
    len=sqrt(n);num=n/len;if(n%len)num++;
    memset(L,0x3f3f3f3f,sizeof(L));
    for(int i=1;i<=n;i++)
    {
        a[i].o=read();a[i].id=i;
        belong[i]=(i-1)/len+1;
        L[belong[i]]=min(L[belong[i]],i);
        R[belong[i]]=max(R[belong[i]],i);
    }
    sort(a+1,a+n+1,cmp1);
    for(int i=1;i<=n;i++)
    {
        a[i].af=a[i-1].af;
        if(a[i].o!=a[i-1].o)a[i].af++,cntt++;
        iid[a[i].af]=a[i].o;
        h[belong[a[i].id]][a[i].af]++;
    }
    sort(a+1,a+n+1,cmp2);
    for(int i=1;i<=cntt;i++)
    {
        for(int j=1;j<=num;j++)
        {
            s[j][i]=s[j-1][i]+h[j][i];
        }
    }
    for(int i=1;i<=num;i++)
    {
        memset(vis,0,sizeof(vis));
        for(int j=i;j<=num;j++)
        {
            int kk=0,kt=0;
            for(int k=L[j];k<=R[j];k++)
            {
                vis[a[k].af]++;
                if(vis[a[k].af]>kk)
                {
                    kk=vis[a[k].af];
                    kt=a[k].af;
                }
            }
            if(kk>vis[p[i][j-1].st]||(kk==vis[p[i][j-1].st]&&kt<p[i][j-1].st))
            {
                p[i][j].num=kk;
                p[i][j].st=kt;
            }
            else
            {
                p[i][j].num=p[i][j-1].num;
                p[i][j].st=p[i][j-1].st;
            }
        }
    }
    while(m--)
    {
        l0=read();r0=read();
        int l=((l0+x-1)%n)+1,r=((r0+x-1)%n)+1;
        if(l>r)swap(l,r);
        x=f(l,r);
        cout<<x<<"\n";
    }
    return 0;
}

by Shadow_Lord @ 2023-07-09 19:53:32

发错了，是这个