CF 455D. Serega and Fun 题解

考虑分块做法。

我们以 \(\sqrt{n}\) 为块长分块，套路地维护每个数在这个每块中的出现次数 \(cnt\)。

对于 2 操作，整块直接读取 \(cnt\)，其余的直接暴力查询。

对于 1 操作，如果在同一个块里，直接暴力去做。如果不在，我们就将最后一个元素插入第一个元素所在的块中，然后整块平移并更新 \(cnt\) 的值，此过程需要用 deque 维护。

特别注意：dq[belong[r]].erase(dq[belong[r]].begin()+r-lx[r]); 会导致 RE，把 r-lx[r] 括起来即可。

/*
 * Title: Serega and Fun
 * Source: 洛谷-CF
 * URL: https://www.luogu.com.cn/problem/CF455D
 * Author: Steven_lzx
 * Command: -std=c++23 -Wall -fno-ms-extensions
 * Date: 2022.11.3
 */
#include <bits/stdc++.h>
using namespace std;
const int MAXN=1e5+5;
int n,t,num,a[MAXN],cnt[350][MAXN],belong[MAXN],ans,q,lx[MAXN],rx[MAXN];
deque<int> dq[350];
int main()
{
    int op,l,r,k,temp;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",a+i);
    t=max(3,(int)sqrt(n));
    num=ceil(n*1.0/t);
    for(int i=1;i<=num;i++)
    {
        for(int j=(i-1)*t+1;j<=min(n,i*t);j++)
        {
            belong[j]=i;
            lx[j]=(i-1)*t+1;
            rx[j]=min(n,i*t);
        }
    }
    /*for(int i=1;i<=n;i++)
        cout<<belong[i]<<' '<<lx[i]<<' '<<rx[i]<<endl;*/
    for(int i=1;i<=n;i+=t)
    {
        for(int j=lx[i];j<=rx[i];j++)
        {
            dq[belong[i]].push_back(a[j]);
            cnt[belong[i]][a[j]]++;
        }
    }
    scanf("%d",&q);
    while(q--)
    {
        scanf("%d",&op);
        if(op==1)
        {
            scanf("%d%d",&l,&r);
            l=(l+ans-1)%n+1;
            r=(r+ans-1)%n+1;
            if(l>r)
                swap(l,r);
            if(belong[l]==belong[r])
            {
                temp=dq[belong[l]][r-lx[l]];
                dq[belong[l]].erase(dq[belong[l]].begin()+(r-lx[l]));//必须加括号，否则 RE，下同
                dq[belong[l]].insert(dq[belong[l]].begin()+(l-lx[l]),temp);
            }
            else 
            {
                dq[belong[l]].insert(dq[belong[l]].begin()+(l-lx[l]),dq[belong[r]][r-lx[r]]);
                cnt[belong[l]][dq[belong[r]][r-lx[r]]]++;
                cnt[belong[r]][dq[belong[r]][r-lx[r]]]--;
                dq[belong[r]].erase(dq[belong[r]].begin()+(r-lx[r]));
                for(int i=belong[l]+1;i<=belong[r];i++)
                {
                    temp=dq[i-1].back();
                    dq[i-1].pop_back();
                    cnt[i-1][temp]--;
                    dq[i].push_front(temp);
                    cnt[i][temp]++;
                }
            }
        }
        else 
        {
            scanf("%d%d%d",&l,&r,&k);
            l=(l+ans-1)%n+1;
            r=(r+ans-1)%n+1;
            k=(k+ans-1)%n+1;
            if(l>r)
                swap(l,r);
            ans=0;
            function<int(int,int,int)> answer=[&](int l,int r,int k)
            {
                int res=0;
                if(belong[l]==belong[r])
                {
                    for(int i=l;i<=r;i++)
                        if(dq[belong[l]][i-lx[l]]==k)
                            res++;
                }
                else 
                {
                    res+=answer(l,rx[l],k);
                    for(int i=belong[l]+1;i<belong[r];i++)
                        res+=cnt[i][k];
                    res+=answer(lx[r],r,k);
                }
                return res;
            };
            printf("%d\n",ans=answer(l,r,k));
        }
    }
    return 0;
}

原文地址：http://www.cnblogs.com/2020gyk080/p/16855668.html