题解 P4168 【[Violet]蒲公英】

· · 题解

提供一种特别简单的思路

就是需要开一个叫做O2优化的东西才能过

大佬都用分块做了，蒟蒻只能离散化

快乐就好

对于这道题，本蒟蒻的想法是现缩小a数组的数据规模，然后再存到b数组中去
毕竟你1e9的数据桶里也存不下 之后每次进行操作的时候只需要找到其在a数组中的位置，再将其映射到b数组中然后输出，即可得到蒲公英的编号。

其实这道题的精华部分是luogu-judger-enable-o2

也许离散化有很多用处但本蒟蒻只会拿来缩小数据规模QAQ

    int a[50001];//原数组；
    int b[50001];//进行去重操作的数组（离散化）并存储a数组的数组；
    int t[50001];//缩小数据范围后拿来存储数据的桶   
    int x=0;//根据题意，第一次操作时x为0；
    int l0,r0;
    int l,r;

读入n,m,a后就可以对其进行离散化操作了。

    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        b[i]=a[i];
    }   
    sort(b+1,b+n+1);
    int sum=unique(b+1,b+n+1)-b-1;
    for(int i=1;i<=n;i++)
    a[i]=lower_bound(b+1,b+sum+1,a[i])-b;//离散化的板子；

操作完毕之后，如果a数组中原来存储的是1,99999,50,50,25,那么现在就变成了1,4,3,3,2;而b数组就存储了1,25,50,99999,50。不难发现，现在的a[2]==4,b[a[2]]==99999,也就与原来的a[2]的值相等。也就是说，我们已经运用离散化缩小了数据规模。

然后我们就可以开始快乐地暴力模拟啦

    while(m--){
        scanf("%d%d",&l0,&r0);
        l=(l0+x-1)%n+1;
        r=(r0+x-1)%n+1;//根据题意进行操作
        if(l>r) swap(l,r);
        for(int i=l;i<=r;i++)
            t[a[i]]++;//桶
        int maxx=0;
        int p=0;
        for(int i=1;i<=sum;i++){
            if(maxx<t[i]){
                maxx=t[i];
                p=i;//记录出现次数最多地蒲公英的位置
            }
        }
        printf("%d\n",b[p]);//输出其在b数组中的编号
        x=b[p];
        memset(t,0,sizeof(t));//每次用完桶记得还原就好啦！QWQ
    }

记得开O2优化不然会TLE4个点

然后我们就在O2的帮助下成功AC啦