题解归档 - cf455D

本文由 cf-code 本地题解库自动归档；公开内容以本地 AC/验证版本为准。

• 本地编号：cf455D
• 本地来源：problems/cf455D/idea.md
• 题目链接：https://codeforces.com/contest/455/problem/D
• 原始标题：455D Serega and Fun

思路

455D Serega and Fun

题意

给定长度 (n) 的数组 (a_i\in[1,n])，(q) 个在线操作（参数经 lastans 解码）：

1. 旋转：区间 ([l,r]) 右旋一位，即 (a[l..r]\to a[r],a[l],...,a[r-1])。
2. 查询：区间 ([l,r]) 内等于 (k) 的元素个数，输出并更新 lastans。

(n,q\le10^5)，值域 (\le n)。

思路

根号分块 + 块状链表：

• 块大小 (B\approx700)，每块维护 vector 元素序列与 cnt[block][v] 频次。
• 旋转 ([l,r])：从位置 (r) 删除尾元素，再插入到位置 (l)（全局下标 1-based）。单次 (O(n/B + B))。
• 查询：整块用 cnt 累加；左右散块暴力扫 vector。
• 每 (B) 次旋转后 rebuild：拍平所有块再均分，防止块大小失衡。

曾尝试「块内 lazy 旋转 + 边界局部旋转」，但相邻两块、无整块中间层时跨块元素无法正确传递（样例 1 首查即错），故弃用。

实现要点

• 在线解码：(l=((l'+lastans-1)\bmod n)+1)，(r,k) 同理；若 (l>r) 则 swap。
• eras(pos) / ins(pos,v)：先定位块（前缀长度），再在 vector 中删/插并维护 cnt。
• rebc 计数达 (B) 时 reb() 重分块。

复杂度

• 单次旋转/查询：均摊 (O(n/B + B))，取 (B\approx\sqrt{n}) 或常数 700 均可过。
• 空间：(O(n + (n/B)\cdot n)) 频次表（值域 (\le n)）。

验证

• 样例 1/2：✅
• 对拍：CF_REMOTE_RUN=0 stress.py cf455D -n 500（Kali 不可达时 WSL 本地编译）

结果

• 待提交 problems/cf455D/solution.cpp
• 模板参考：lib/数据结构(分块).cpp（本题实现为块状链表 + 频次，比模板更完整）

代码

来源：problems/cf455D/solution.cpp

/* Author: likely
 * Time: 2026-06-08 04:35:58
**/
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll maxn=100005;
const ll maxb=400;
ll cnt[maxb+5][maxn+5],n,q,nb,B,i,j,k,l,r,zc,pd,dq,op,ans,rebc;
vector<ll>blk[maxb+5];
void reb(){
    vector<ll>all;
    ll u,v;
    for(i=0;i<nb;i++)
        for(j=0;j<(ll)blk[i].size();j++) all.push_back(blk[i][j]);
    nb=(n+B-1)/B;
    for(i=0;i<nb;i++){
        blk[i].clear();
        for(j=1;j<=n;j++) cnt[i][j]=0;
    }
    for(i=0;i<(ll)all.size();i++){
        zc=i/B;
        blk[zc].push_back(all[i]);
        cnt[zc][all[i]]++;
    }
}
ll eras(ll pos){
    ll bid,idx,v,cur=0;
    for(bid=0;bid<nb;bid++){
        pd=(ll)blk[bid].size();
        if(pos<=cur+pd){
            idx=pos-cur-1;
            v=blk[bid][idx];
            cnt[bid][v]--;
            blk[bid].erase(blk[bid].begin()+idx);
            return v;
        }
        cur+=pd;
    }
    return 0;
}
void ins(ll pos,ll v){
    ll bid,idx,cur=0;
    for(bid=0;bid<nb;bid++){
        pd=(ll)blk[bid].size();
        if(pos<=cur+pd+1){
            idx=pos-cur-1;
            blk[bid].insert(blk[bid].begin()+idx,v);
            cnt[bid][v]++;
            return;
        }
        cur+=pd;
    }
}
void shf(ll l,ll r){
    pd=eras(r);
    ins(l,pd);
    rebc++;
    if(rebc>=B) reb(),rebc=0;
}
ll qry(ll l,ll r,ll v){
    ll cur=0,ret=0,bid;
    for(bid=0;bid<nb;bid++){
        pd=(ll)blk[bid].size();
        zc=cur+1;
        dq=cur+pd;
        if(zc>=l and dq<=r) ret+=cnt[bid][v];
        else if(zc<=r and dq>=l){
            for(j=0;j<pd;j++){
                if(cur+j+1>=l and cur+j+1<=r and blk[bid][j]==v) ret++;
            }
        }
        cur+=pd;
    }
    return ret;
}
int main(){
    ll lp,rp,kp;
    cin>>n;
    B=max(1ll,(ll)sqrt(n));
    for(i=1;i<=n;i++){
        cin>>zc;
        pd=(i-1)/B;
        blk[pd].push_back(zc);
        cnt[pd][zc]++;
    }
    nb=(n+B-1)/B;
    cin>>q;
    ans=0,rebc=0;
    while(q--){
        cin>>op>>lp>>rp;
        l=((lp+ans-1)%n)+1;
        r=((rp+ans-1)%n)+1;
        if(l>r) swap(l,r);
        if(op==1) shf(l,r);
        else{
            cin>>kp;
            k=((kp+ans-1)%n)+1;
            ans=qry(l,r,k);
            cout<<ans<<"\n";
        }
    }
    return 0;
}