P1067 象群回响簿 官方题解

【部分分：测试点 1∼41\sim 41∼4】

• 一个显然的思路是对每个询问重新扫描区间 $[l,r]$，统计其中每个数字的出现次数。随后枚举出现过的不同数字 $x$，检查其出现次数是否恰好为 $x$。
• 使用数组或离散化后的计数表即可完成。总时间复杂度为 $\mathcal{O}(nm)$，空间复杂度为 $\mathcal{O}(n)$。当询问区间很长且询问数量很多时，重复统计成为瓶颈。

【部分分：测试点 5∼85\sim 85∼8】

• 特殊性质 A 保证 $a_i\leq 20$。对每个 $1\leq x\leq 20$，预处理数字 $x$ 的出现次数前缀和 $p_{x,i}$。
• 对询问 $[l,r]$，枚举 $x=1,2,\ldots,20$，检查 $p_{x,r}-p_{x,l-1}=x$。时间复杂度为 $\mathcal{O}(20(n+m))$，空间复杂度为 $\mathcal{O}(20n)$。

【部分分：测试点 9∼129\sim 129∼12】

• 特殊性质 B 保证每个询问的长度不超过 $100$。仍然使用第一档的直接统计，但只扫描询问区间中的至多 $100$ 个位置。
• 处理一个询问后，只清空本次出现过的数字，避免每次清空完整值域。总时间复杂度为 $\mathcal{O}(100m)$，空间复杂度为 $\mathcal{O}(n)$。

【正解】

• 前几档的做法仍然会为不同询问重复统计公共部分。考虑到相邻询问往往有很长的公共区间，我们可以使用莫队调整当前区间。按照左端点所在块排序，同一块内再按照右端点排序。使用奇偶块反向排序右端点可以进一步减少指针移动。

• 令 $c_x$ 表示数字 $x$ 在当前区间中的出现次数，令 $Ans$ 表示满足 $c_x=x$ 的不同数字数量。因为区间长度不超过 $n$，所有 $x>n$ 都不可能成为回响数字，可以直接忽略。

• 加入一个值 $x$ 前，若 $c_x=x$，先令 $Ans\gets Ans-1$。随后令 $c_x\gets c_x+1$，若新的 $c_x=x$，再令 $Ans\gets Ans+1$。删除一个值时按照完全相同的顺序先撤销旧贡献、修改计数、再加入新贡献。

• 每次指针移动只进行常数次操作，因此块长取 $\Theta(\sqrt n)$ 时，单组数据的时间复杂度为 $\mathcal{O}((n+m)\sqrt n)$，空间复杂度为 $\mathcal{O}(n+m)$。多组数据之间只需清空出现过的计数与询问答案。

• 还可以按照询问右端点离线处理。将数字 $x$ 在前缀 $[1,r]$ 中的出现位置依次记为 $p_{x,1},p_{x,2},\ldots,p_{x,c_x}$，并令 $p_{x,0}=0$。若 $c_x\geq x$，那么区间 $[l,r]$ 中数字 $x$ 恰好出现 $x$ 次，当且仅当

• 因此，在右端点 $r$ 固定时，数字 $x$ 会对左端点区间

中的每一个位置贡献 $1$。所有数字的贡献相加，就是询问 $[l,r]$ 的答案。

• 扫描到位置 $r$ 时，只有 $x=a_r$ 的出现次数发生变化。若加入 $r$ 以前 $x$ 已经产生贡献，就先把旧的左端点区间减去 $1$，随后记录新的出现位置，再把新的左端点区间加上 $1$。由于区间长度不超过 $n$，$x>n$ 时可以直接忽略。
• 使用树状数组维护左端点上的差分。对区间 $[L,R]$ 加上 $v$，只需在 $L$ 处加上 $v$，在 $R+1$ 处减去 $v$。将询问按照右端点归类，扫描到 $r$ 后，查询位置 $l$ 的前缀和即可得到 $[l,r]$ 的答案。
• 每次加入元素至多产生两次区间修改，每个询问只进行一次单点查询。单组数据的时间复杂度为 $\mathcal{O}((n+m)\log n)$，空间复杂度为 $\mathcal{O}(n+m)$。

【参考代码】

1#include <cstdio>2#include <vector>3 4#define MAXN 1000105 6using namespace std;7 8int c,T,n,m,Tree[MAXN];9 10void Add(int Pos,int Val){11    for(int i=Pos;i<=n+1;i+=i&-i) Tree[i]+=Val;12}13 14int Query(int Pos){15    int Ret=0;16    for(int i=Pos;i;i-=i&-i) Ret+=Tree[i];17    return Ret;18}19 20void Modify(int l,int r,int Val){21    if(l>r) return;22    Add(l,Val);23    Add(r+1,-Val);24}25 26void Solve(){27    scanf("%d%d",&n,&m);28    vector <int> Line(n+1),Ans(m+1);29    vector <vector<int> > Pos(n+1);30    vector <vector<pair<int,int> > > Ask(n+1);31    for(int i=1;i<=n+1;i++) Tree[i]=0;32    for(int i=1;i<=n;i++) scanf("%d",&Line[i]);33    for(int i=1,l,r;i<=m;i++){34        scanf("%d%d",&l,&r);35        Ask[r].push_back(make_pair(l,i));36    }37    for(int r=1;r<=n;r++){38        int x=Line[r];39        if(x<=n){40            int Count=Pos[x].size();41            if(Count>=x){42                int l=(Count==x?1:Pos[x][Count-x-1]+1);43                int rr=Pos[x][Count-x];44                Modify(l,rr,-1);45            }46            Pos[x].push_back(r);47            Count++;48            if(Count>=x){49                int l=(Count==x?1:Pos[x][Count-x-1]+1);50                int rr=Pos[x][Count-x];51                Modify(l,rr,1);52            }53        }54        for(int i=0;i<(int)Ask[r].size();i++){55            Ans[Ask[r][i].second]=Query(Ask[r][i].first);56        }57    }58    for(int i=1;i<=m;i++) printf("%d\n",Ans[i]);59}60 61int main(){62    scanf("%d%d",&c,&T);63    while(T-->0) Solve();64    return 0;65}