[CF1819D] Misha and Apples

Misha and Apples
只能做做评分虚高的题了,头痛浪费了一节晚自习。
但是为什么机房的同学们都觉得2500~2800算水题呢?
最终的答案一定是 \([S_1,S_x]\) 被清空,\([S_{x+1},S_n]\) 被全部放入集合。
若 \(\exists i\in[x+1,n],k_i=0\),答案为 m,否则为 \(\sum_{i=x+1}^nk_i\)。
枚举到 i 时 x 的最小值,则上式的 x 即 i=n 时的 x。
设 \(f_i\) 表示加入 \(S_i\) 后集合是否能清空,\(ma\) 表示 \(S_i\) 中的数上一次出现最晚的位置。
设 \(x<ma\),此时 \([S_x,S_{i-1}]\) 加入 \(S_i\) 后可以清空,\(f_i=1\)。
否则如果 \(\exists j\in[x+1,i-1],k_j=0\),这个商店可以加入 \(S_i\) 中的数使其清空,\(f_i=1\)。
考虑 x 的移动,当 \(x<ma\) 或 \(f_x=0\) 时,x++。

#include<cstdio>
#include<vector>
#include<iostream>
using namespace std;
const int MAXN=2e5+5;
int T,n,m,wz,id[MAXN],pre[MAXN];
bool f[MAXN];
vector<int> v[MAXN];
int main(){
	scanf("%d",&T);f[0]=1;
	while(T--){
		scanf("%d%d",&n,&m);for(int i=1;i<=n;i++) f[i]=0;wz=0;
		for(int i=1,x;i<=n;i++){
			scanf("%d",&x);v[i].clear();
			pre[i]=pre[i-1]+(x==0);
			for(int j=1,y;j<=x;j++){
				scanf("%d",&y);id[y]=0;v[i].push_back(y);
			}
		}
		for(int i=1;i<=n;i++){
			int ma=0;
			for(int j=0;j<v[i].size();j++){
				int u=v[i][j];ma=max(ma,id[u]);id[u]=i;	
			}
			f[i]=(wz<ma)||(pre[i]!=pre[wz]);
			while(wz<ma||(!f[wz])) wz++;
		}
		if(pre[wz]!=pre[n]){printf("%d\n",m);continue;}
		int tmp=0;
		for(int i=wz+1;i<=n;i++) tmp+=(int)v[i].size();
		printf("%d\n",tmp);
	}
	return 0;
}