P4168 [Violet]蒲公英

题目

P4168 [Violet]蒲公英

独立打完黑题代码(应该是这题比较水)

做法

强制在线，我们用分块

预处理求出第(i)块到第(j)块的众数，前(i)块(j)值出现的次数

剩下的不想说了，应该都能猜到吧？？？

My complete code

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
typedef int LL;
const LL maxn=40009;
const LL inf=0x3f3f3f3f;
inline LL Read(){
    LL x(0),f(1);char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+c-'0',c=getchar();
    return x*f;
}
LL n,tot,T,lst;
LL a[maxn],belong[maxn],visit[maxn],b[maxn];
struct node{
    LL l,r;
    LL col[maxn];
}P[205];
LL sum[205][maxn];
struct Z{
    LL num,id;
}zhong[205][205];
inline void First(){
    LL size=sqrt(n),pieces=ceil((double)n/size);
    for(LL i=1;i<=pieces;++i){
        P[i].l=(i-1)*size+1; P[i].r=min(i*size,n);
        for(LL j=P[i].l;j<=P[i].r;++j)
            belong[j]=i,
            ++P[i].col[a[j]];
    }
    for(LL i=1;i<=pieces;++i)
        for(LL j=1;j<=tot;++j)
            sum[i][j]=sum[i-1][j]+P[i].col[j];
    for(LL i=1;i<=pieces;++i){
        memset(visit,0,sizeof(visit));
        for(LL j=i;j<=pieces;++j){
            zhong[i][j]=zhong[i][j-1];
            for(LL it=P[j].l;it<=P[j].r;++it){
                LL now(a[it]);++visit[now];
                if(visit[now]>zhong[i][j].num||(visit[now]==zhong[i][j].num&&now<zhong[i][j].id))
                    zhong[i][j]=(Z){visit[now],now};
            }
        }
    }
}
inline void Solve(LL l,LL r){
    LL ans(0),num(0);
    memset(visit,0,sizeof(visit));
    if(belong[l]!=belong[r]){
        LL lt=belong[l]+1,rt=belong[r]-1;
        ans=zhong[lt][rt].id,num=zhong[lt][rt].num;
        for(LL i=l;i<=P[lt].l-1;++i){
            ++visit[a[i]];
            LL now(visit[a[i]]+sum[rt][a[i]]-sum[lt-1][a[i]]);
            if(now>num||(now==num&&a[i]<ans))
                ans=a[i],
                num=now;
        }
        for(LL i=P[rt].r+1;i<=r;++i){
            ++visit[a[i]];
            LL now(visit[a[i]]+sum[rt][a[i]]-sum[lt-1][a[i]]);
            if(now>num||(now==num&&a[i]<ans))
                ans=a[i],
                num=now;
        }
    }else
        for(LL i=l;i<=r;++i){
            ++visit[a[i]];
            if(visit[a[i]]>num||(visit[a[i]]==num&&a[i]<ans))
                ans=a[i],
                num=visit[a[i]];
        }
    printf("%d
",lst=b[ans]);
}
int main(){
    n=Read(),T=Read();
    for(LL i=1;i<=n;++i)
        a[i]=b[i]=Read();
    sort(b+1,b+1+n),tot=unique(b+1,b+1+n)-b-1;
    for(LL i=1;i<=n;++i)
        a[i]=lower_bound(b+1,b+1+tot,a[i])-b;
    First();
    while(T--){
        LL l(Read()),r(Read());
        l=(LL)(1ll*l+lst-1)%n+1,r=(LL)(1ll*r+lst-1)%n+1;
        if(l>r)swap(l,r);
        Solve(l,r);
    }
    return 0;
}/*
*/