思路
这是一道交互题。
交互格式在这里就不说了。
考虑到：若 \([l,r]\) 这个区间是合法的，那么因为 \([1,l]\) 是合法的，所以 \([1,r]\) 是合法的，所以问题转化为，有多少个前缀是合法的。
对于一段区间，若所有的数要么出现 \(0\) 次，要么出现了 \(M\) 次，那么这就是合法的条件之一（要么都没记录，要么全记录）。这个可以用桶来实现。
还有就是掉叶子是否合法。假如这段区间中，存在一个非叶子节点的儿子没有掉完，并且他自己要掉，那么就是非法的，这个可以通过记录每个点的未掉的儿子个数，以及这个点是否需要掉来解决。
当满足以上两个条件时，这个前缀便是合法的，将答案 \(+1\) 即可。
时间复杂度 \(O(NM)\)。
代码
注意是交互题。
#include<bits/stdc++.h>
using namespace std;
int solve(int N,int M,vector<int> F,vector<vector<int> >S);
const int MAXN=1e5+10;
int cnt,cnt2,ans,son[MAXN],t[MAXN];
bool flag[MAXN];
int solve(int N,int M,vector<int> F,vector<vector<int> >S){
for(int i=0;i<N;i++) son[i]=t[i]=flag[i]=0;
for(int i=1;i<N;i++) son[F[i]]++;
cnt=N;cnt2=ans=0;
for(int i=0;i<N-1;i++){
for(int j=0;j<M;j++){
t[S[j][i]]++;
if(t[S[j][i]]==1) cnt--;
if(t[S[j][i]]==M) cnt++;
if(flag[S[j][i]]) continue;
flag[S[j][i]]=true;
if(son[S[j][i]]!=0) cnt2++;
son[F[S[j][i]]]--;
if(son[F[S[j][i]]]==0&&flag[F[S[j][i]]]) cnt2--;
}
if(cnt==N&&cnt2==0) ans++;
}
return ans;
}