题解归档 - cf220B

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

• 本地编号：cf220B
• 本地来源：problems/cf220B/idea.md
• 题目链接：https://codeforces.com/contest/220/problem/B
• 原始标题：220B Little Elephant and Array

思路

220B Little Elephant and Array

题意

给定长度 (n) 的数组 (a) 与 (m) 个区间查询 ([l,r])。对每个查询，统计有多少个正整数 (x)，使得 (x) 在子数组 (a_l,\ldots,a_r) 中恰好出现 (x) 次。

(n,m \le 10^5)，(a_i \le 10^9)。

思路

Mo 算法（离线区间查询）。

维护当前窗口 ([L,R]) 内每个值的频次 cnt[v]，以及满足 cnt[v]==v 的值的个数 ans。

• 加入 (x)：若旧频次等于 (x) 则 ans--；频次加一后若新频次等于 (x) 则 ans++。
• 删除 (x)：对称处理。

关键观察：若 (x > n)，窗口内最多 (n) 次出现，不可能满足 cnt[x]==x，故 ans 只需在 (x \le n) 时更新；(x > n) 的频次用 unordered_map 维护即可（不影响答案）。

查询按 Mo 排序：块大小 (B \approx \sqrt n)，先按 (\lfloor l/B \rfloor)，同块内按 (r) 奇偶块交替升降序，减少指针移动。

模板

见 lib/数据结构(Mo算法).cpp（lib_target）。

void mo_add(ll x){
    if(x<=maxn){
        if(cnt[x]==x) ans--;
        cnt[x]++;
        if(cnt[x]==x) ans++;
    }else mp[x]++;
}

复杂度

• 排序：(O(m \log m))
• 指针移动总次数 (O((n+m)\sqrt n))，每次 (O(1)) 均摊
• 空间：(O(n))

验证

• 样例：✅
• 对拍 stress.py -n 500：368+ 组 OK，无 WA（Kali SSH 偶发断连中断脚本，非答案错误）

链接

https://codeforces.com/contest/220/problem/B

代码

来源：problems/cf220B/solution.cpp

/* Author: likely
 * Time: 2026-06-08 02:41:30
**/
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll maxn=100005;
struct query{ll l,r,id;};
vector<query>qq;
unordered_map<ll,ll>cccc;
ll a[maxn+5],bel[maxn+5],ans[maxn+5],n,m,dq,cur,ansc;
bool cmp(query u,query v){
    if(bel[u.l]!=bel[v.l]) return bel[u.l]<bel[v.l];
    if(bel[u.l]&1) return u.r<v.r;
    return u.r>v.r;
}
void add(ll x){
    ll zc=a[x],pd=0;
    if(cccc.count(zc)) pd=cccc[zc];
    if(pd==zc) ansc--;
    cccc[zc]=pd+1;
    if(pd+1==zc) ansc++;
}
void del(ll x){
    ll zc=a[x],pd=cccc[zc];
    if(pd==zc) ansc--;
    cccc[zc]=pd-1;
    if(cccc[zc]==0) cccc.erase(zc);
    if(pd-1==zc) ansc++;
}
int main(){
    ll i,j,k,l,r;
    cin>>n>>m;
    dq=sqrt(n);
    if(dq<1) dq=1;
    for(i=1;i<=n;i++){
        cin>>a[i];
        bel[i]=(i-1)/dq;
    }
    qq.resize(m);
    for(i=0;i<m;i++){
        cin>>qq[i].l>>qq[i].r;
        qq[i].id=i;
    }
    sort(qq.begin(),qq.end(),cmp);
    l=1,r=0;
    for(i=0;i<m;i++){
        while(l>qq[i].l) add(--l);
        while(r<qq[i].r) add(++r);
        while(l<qq[i].l) del(l++);
        while(r>qq[i].r) del(r--);
        ans[qq[i].id]=ansc;
    }
    for(i=0;i<m;i++){
        cout<<ans[i]<<endl;
    }
    return 0;
}