题解 P4168 【[Violet]蒲公英】

laduiw · 2018-08-10 17:20:40 · 题解

分块

算是比较简单的一道黑题，思路依然是分块，但是稍有差别

把序列a分成t块，每段len=n/t
对于询问[l,r]，设l处于tl块，r处于tr块，把[l,r]分为三段，左边不足的+中间整的+右边多的
显然对于[l,r]中的众数只有两种可能在中间整块中或是两边零散的数

到这里都是一样的，但是其他题解貌似保存了所有以块边界为端点的数出现的次数，这样复杂度变为nt^2，这里提供另一种思路。

Solution

1. 我们只记录f[i][j]，表示i块到j块的众数（离散之后的值），假设你已经知道怎么nt求出
2.对于整区间，算出这个众数以及他出现的次数,可以用下面的方法二分这个众数在这整段区间出现次数。
3.对于零散的两边的数，暴力枚举每一个，但怎么知道它在[l,r]之间出现的次数呢？
可以对每个离散后的数值建一个vector，记录它每次出现的位置，因为是一位一位加，每个vector内一定是单调递增的，然后假设你想知道k这个数在[l,r]出现的次数，就在k这个vector二分第一个>=l的数，最后一个<=r的数，这两个下标相减+1，就是出现次数。
举个例子，a={2,3,3,2,4,2,1,1,2,4},你想求2在[3,10]出现次数，2的vector={1,4,6,9}，二分出第一个>=3的下标，得到2,最后一个<=10的下标，得到4,这样出现次数=4-2+1=3
现在唯一问题就是怎么求f[i][j]
可以枚举每一个块i，以这个块左端点为起点，向后延伸，记录sum[k]数组表k这种数出现次数，假设向右延伸到j,sum[c[j]]++,(c[j]是j离散后的值)，然后用maxx表示出现最多的数出现次数，ans记录出现最多的数，每次用sum[j]跟新maxx,ans跟着变，最后f[i][id[j]]=ans（这一步仔细体会一下，f[i][id[j]]会被赋值多次但最后一定是最优的）
最后考虑复杂度求f数组nt，每次询问 len*log(n)所以总复杂度nt+n/t*log(n),所以t=sqrt(n*log(n))最优.

#include<bits/stdc++.h>
using namespace std;
const int maxn=40010,maxt=1000;
vector <int> ed[maxn];
int a[maxn],b[maxn],c[maxn],sum[maxn],f[maxt][maxt],id[maxn],p,len,t;
//c是离散后的数组，id是i这个点所在编号 ,t是块数,len是每块长度 
int n,m,l[maxt],r[maxt];
void prework(int x)//求f[i][j],当前在x这个块 
{
    int maxx=0,ans=0;
    memset(sum,0,sizeof(sum));//每次都要清空 
    for (int i=(x-1)*len+1;i<=n;i++)//从这个块左端点一位一位向后移动 
    {
        sum[c[i]]++;
        if (maxx<sum[c[i]] ||(maxx==sum[c[i]] && b[c[i]]<b[ans]))//如果编号小也可以 
        {
            ans=c[i];
            maxx=sum[c[i]];
        }
        f[x][id[i]]=ans;
    }
}

int chal(int x,int g,int h)//二分最左边下标 
{
    int ll=0,rr=ed[x].size()-1;
    while (rr>ll)
    {
        int mid=(ll+rr)>>1;
        if (ed[x][mid]>=g) rr=mid;
            else ll=mid+1;
    }
    return rr;
}

int chair(int x,int g,int h)//二分最右边下标 
{
    int ll=0,rr=ed[x].size()-1;
    while (rr>ll)
    {
        int mid=(ll+rr+1)>>1;//细节，不加1会死循环,如果l=4,r=5,mid=4,ed[x][mid]<=h,l=4就死循环了 
        if (ed[x][mid]<=h) ll=mid;
            else rr=mid-1;
    }
    return ll;
}

int askl(int al,int ar)
{
    int tl=id[al],tr=id[ar];
    if (tl+1>=tr-1) {//如果这段太小，也就是没有中间整段 
        int maxx=0,ans=0;
        for (int i=al;i<=ar;i++)
            {
                int pl=chal(c[i],al,ar),pr=chair(c[i],al,ar);
                if (maxx<pr-pl+1 || (maxx==pr-pl+1 && b[c[i]]<b[ans]))
                {
                    ans=c[i];
                    maxx=pr-pl+1;
                } 
            }
        return b[ans];
    }
    int ans=f[tl+1][tr-1];//中间整块的众数 
    int maxx=chair(ans,l[tl+1],r[tr-1])-chal(ans,l[tl+1],r[tr-1])+1;//ans的出现次数 
    for (int i=al;i<=r[tl];i++)//处理左边零散块 
    {
        int pl=chal(c[i],al,ar),pr=chair(c[i],al,ar);
        if (maxx<pr-pl+1 || (maxx==pr-pl+1 && b[c[i]]<b[ans]))
        {
            ans=c[i];
            maxx=pr-pl+1;
        } 
    }
    for (int i=l[tr];i<=ar;i++)//处理右边零散块 
    {
        int pl=chal(c[i],al,ar),pr=chair(c[i],al,ar);
        if (maxx<pr-pl+1 || (maxx==pr-pl+1 && b[c[i]]<b[ans]))
        {
            ans=c[i];
            maxx=pr-pl+1;
        } 
    }
    return b[ans];
}

int main()
{
    memset(a,0,sizeof(a));
    memset(f,0,sizeof(f));
    scanf("%d %d",&n,&m);
    for (int i=1;i<=n;i++) scanf("%d",&a[i]),b[i]=a[i];
    t=sqrt(n*log(n));
    len=n/t; 
    for (int i=1;i<=t;i++)
    {
        if (i*len>n) break;//块太大就不要 
        l[i]=(i-1)*len+1;
        r[i]=i*len;
    }
    if (r[t]<n) {
        t++;l[t]=r[t-1]+1;r[t]=n;//最后一段独立成块 
    }
    for (int i=1;i<=t;i++)
        for (int j=l[i];j<=r[i];j++)
            id[j]=i;
    sort(b+1,b+n+1);
    int q=unique(b+1,b+n+1)-(b+1);
    for (int i=1;i<=n;i++)
        c[i]=lower_bound(b+1,b+q+1,a[i])-b;//离散化，这里使用排序后第一次出现位置做离散值 
    for (int i=1;i<=n;i++)
        ed[c[i]].push_back(i);//每种数加下标 
    for (int i=1;i<=t;i++)
        prework(i);
    for (int i=1;i<=m;i++)
    {
        int l0,r0;
        scanf("%d %d",&l0,&r0);
        l0=(l0+p-1)%n+1;r0=(r0+p-1)%n+1;//强制在线 
        if (l0>r0) swap(l0,r0);
        p=askl(l0,r0);
        printf("%d\n",p);
    }
    return 0;
}

//细节还是蛮多的，祝诸君好运