[学习笔记]P4168 [Violet]蒲公英（分块+二分）

Owen_codeisking · 2018-07-10 07:54:10 · 个人记录

P4168 [Violet]蒲公英

题目提供者 kkksc03 站长团

评测方式云端评测

标签众数块状链表,块状数组,分块枚举,暴力离散化

难度 NOI/NOI+/CTSC

时空限制 2000ms / 512MB

题目背景

亲爱的哥哥：

你在那个城市里面过得好吗？

我在家里面最近很开心呢。昨天晚上奶奶给我讲了那个叫「绝望」的大坏蛋的故事的说！它把人们的房子和田地搞坏，还有好多小朋友也被它杀掉了。我觉得把那么可怕的怪物召唤出来的那个坏蛋也很坏呢。不过奶奶说他是很难受的时候才做出这样的事的……

最近村子里长出了一大片一大片的蒲公英。一刮风，这些蒲公英就能飘到好远的地方了呢。我觉得要是它们能飘到那个城市里面，让哥哥看看就好了呢！

哥哥你要快点回来哦！

爱你的妹妹 Violet

Azure 读完这封信之后微笑了一下。

“蒲公英吗……”

题目描述

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

为了简化起见，我们把所有的蒲公英看成一个长度为n的序列 (a_{1},a_{2},...,a_{n})为一个正整数，表示第i棵蒲公英的种类编号。

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

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

输入格式：

第一行两个整数 n,m ，表示有n株蒲公英，m 次询问。

接下来一行n个空格分隔的整数a_{i}，表示蒲公英的种类

再接下来m 行每行两个整数l_{0}，r_{0}我们令上次询问的结果为 x（如果这是第一次询问，则 x=0）。

令l=(l_{0}+x-1)modn +1,r=(r_{0}+x-1)modn +1,如果 l>r，则交换 l,r 。

最终的询问区间为[l,r]。

输出格式：

输出m 行。每行一个整数，表示每次询问的结果。

输入输出样例

输入样例#1：

6 3

1 2 3 2 1 2

1 5

3 6

1 5

输出样例#1：

说明

对于 20% 的数据，保证 1<=n,m<=3000

对于 100% 的数据，保证1<=n<=40000,1<=m<=50000,1<=a_{i}<=10^9。

Code Below:

// luogu-judger-enable-o2
/*
感觉这道题还是很好的，就是自己
有几个点写错了，比如a[i].sum写成
a[i].l，初始化前忘了sort... 
vector大法好！
*/
#include <bits/stdc++.h>
using namespace std;
int n,m;
struct node
{
    int sum,l;
}a[100010];
int b[100010],rnk[100010],t;
int pos[100010];
int vis[100010],f[1010][1010];
vector<int> q[100010];
bool cmp1(node a,node b){return a.sum<b.sum;}
bool cmp2(node a,node b){return a.l<b.l;}

void init(int x)
{
    int ans=0,Max=0;
    memset(vis,0,sizeof(vis));
    for(int i=(x-1)*t+1;i<=n;i++){
        vis[a[i].sum]++;
        if(vis[a[i].sum]>Max) Max=vis[a[i].sum],ans=a[i].sum;
        else if(vis[a[i].sum]==Max&&a[i].sum<ans) ans=a[i].sum;
        f[x][pos[i]]=ans;
    }
}

int find(int l,int r,int i)
{
    vector<int>::iterator x=upper_bound(q[i].begin(),q[i].end(),r);
    vector<int>::iterator y=lower_bound(q[i].begin(),q[i].end(),l);
    return x-y;
}

int query(int l,int r){
    int u=pos[l],v=pos[r];
    int ans=f[u+1][v-1];
    int Max=find(l,r,ans);
    for(int i=l;i<=min(r,u*t);i++){
        int s=find(l,r,a[i].sum);
        if(s>Max) Max=s,ans=a[i].sum;
        else if(s==Max&&a[i].sum<ans) ans=a[i].sum;
    }
    if(u!=v){
        for(int i=(v-1)*t+1;i<=r;i++){
            int s=find(l,r,a[i].sum);
            if(s>Max) Max=s,ans=a[i].sum;
            else if(s==Max&&a[i].sum<ans) ans=a[i].sum;
        }
    }
    return ans;
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) scanf("%d",&a[i].sum),a[i].l=i;
    sort(a+1,a+n+1,cmp1);
    int tot=0;t=sqrt(n);
    for(int i=1;i<=n;i++){
        if(a[i-1].sum!=a[i].sum)
            tot++;
        b[i]=tot;
        rnk[tot]=a[i].sum;
    }
    for(int i=1;i<=n;i++) a[i].sum=b[i];
    sort(a+1,a+n+1,cmp2);
    for(int i=1;i<=n;i++) q[a[i].sum].push_back(i);
    for(int i=1;i<=n;i++) pos[i]=(i-1)/t+1;
    for(int i=1;i<=pos[n];i++)
        init(i);
    int x=0;
    for(int i=1;i<=m;i++){
        int l,r;
        scanf("%d %d",&l,&r);
        l=(l+x-1)%n+1,r=(r+x-1)%n+1;
        if(l>r) swap(l,r);
        x=rnk[query(l,r)];
        printf("%d\n",x);
    }
    return 0;
}