luogu P4168 蒲公英+ 分块学习笔记

## [ 传送门 ](https://www.luogu.org/problemnew/show/P4168)

题目描述

在乡下的小路旁种着许多蒲公英，而我们的问题正是与这些蒲公英有关。

为了简化起见，我们把所有的蒲公英看成一个长度为n的序列\((a_1,a_2..a_n)\)，其中 \(a_i\)为一个正整数，表示第i棵蒲公英的种类编号。

而每次询问一个区间 [l,r]，你需要回答区间里出现次数最多的是哪种蒲公英，如果有若干种蒲公英出现次数相同，则输出种类编号最小的那个。

注意，你的算法必须是在线的

Solution

Code 

#include<bits/stdc++.h>

#define max(a,b) ((a)>(b)?(a):(b))

#define min(a,b) ((a)<(b)?(a):(b))

inline int read()

{

    int x=0,f=1;char ch=getchar();

    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

    while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}

    return x*f;

}

#define MN 40005

int N,M,col[MN],fcol[MN],tt[MN],tot;

int T,pos[MN],a[205][205],num[MN][205],L[MN],R[MN];

inline void init()

{

    register int i,j;

    std::sort(tt+1,tt+tot+1);

    tot=std::unique(tt+1,tt+tot+1)-tt-1;

    for(i=1;i<=N;++i)

    {

        int p=col[i];

        col[i]=std::lower_bound(tt+1,tt+tot+1,col[i])-tt;

        fcol[col[i]]=p;

    }

    for(i=N;i>=1;--i)

    {

        if(pos[i]==pos[i-1]) continue;

        L[pos[i]]=i;

        register int ans=0,bl=pos[i];

        for(j=i;j<=N;++j)

        {

            num[col[j]][bl]++;

            if(num[col[j]][bl]>num[ans][bl]) ans=col[j];

            if(num[col[j]][bl]==num[ans][bl]&&col[j]<ans) ans=col[j];

            if(pos[j]!=pos[j+1]) R[pos[j]]=j,a[pos[i]][pos[j]]=ans;

        }

    }

    memset(num,0,sizeof num);

    for(i=1;i<=N;++i)

    {

        num[col[i]][pos[i]]++;

        if(pos[i]!=pos[i+1]&&i!=N)

        for(j=1;j<=tot;++j) num[j][pos[i]+1]=num[j][pos[i]];

    }

}

int tmp[MN];

bool vis[MN];

inline int query(int l,int r)

{

    memset(tmp,0,sizeof tmp);

    memset(vis,0,sizeof vis);

    register int i,ll,rr,ans=0;

    ll=pos[l]+(l!=L[pos[l]]);

    rr=pos[r]-(r!=R[pos[r]]);

    if(l!=L[pos[l]])

        for(i=l;i<=R[pos[l]];++i)

        {

            tmp[col[i]]++;

            if(!vis[col[i]]) vis[col[i]]=true,tmp[col[i]]+=num[col[i]][rr]-num[col[i]][ll-1];

            if(tmp[col[i]]>tmp[ans]||(tmp[ans]==tmp[col[i]]&&col[i]<ans)) ans=col[i];

        }

    if(r!=R[pos[r]])

        for(i=L[pos[r]];i<=r;++i)

        {

            tmp[col[i]]++;

            if(!vis[col[i]]) vis[col[i]]=true,tmp[col[i]]+=num[col[i]][rr]-num[col[i]][ll-1];

            if(tmp[col[i]]>tmp[ans]||(tmp[ans]==tmp[col[i]]&&col[i]<ans)) ans=col[i];

        }

    register int o=a[ll][rr],numo=num[o][rr]-num[o][ll-1];

//	printf("ll=%d rr=%d o=%d\n",ll,rr,o);

    if(!vis[o]&&(numo>tmp[ans]||(numo==tmp[ans]&&o<ans))) ans=o;

    return fcol[ans];

}

int main()

{

//	freopen("testdata.in","r",stdin);

//	freopen("tesedata.out","w",stdout);

    N=read();M=read();

    register int i;T=(int)(sqrt(N));

    for(i=1;i<=N;++i) col[i]=read(),pos[i]=(i-1)/T+1,tt[++tot]=col[i];

    init();

    int l,r,x=0;

//	L=(l0-1+x) mod n +1,R = (r0-1 + x ) mod n +1

    while(M--)

    {

        l=read();r=read();

        l=(l-1+x)%N+1,r=(r-1+x)%N+1;

        if(l>r) std::swap(l,r);

//		printf("%d %d\n",l,r);

        x=query(l,r);

        printf("%d\n",x);

    }

    return 0;

}

---

Blog来自PaperCloud，未经允许，请勿转载，TKS！