求各位佬佬帮看看哪里错了
思路是求出 fi 表示前 i 个集合搞完是否可能使得 S 为空;mai 表示 mai∼i 这些集合中没有重复元素,且使得 mai 最小(双指针求)。
个人认为问题可能出在求最终答案的部分:枚举最后一次 S 为空的位置 t,man−1≤t≤n,需要满足 ft=1,若 t+1∼n 中有 ki=0 的,答案为 m,否则答案为 i=t+1∑nki。
#include <bits/stdc++.h>
std::vector <int> a[200005];
int n, m, k[200005], ans, f[200005], las[200005], ma[200005], buc[200005], cnt;
std::set <int> S, P;
void solve(){
scanf("%d%d", &n, &m); S.clear(); P.clear();
for(int i = 1; i <= n; ++i) f[i] = 0;
f[0] = 1; ans = 0; cnt = 0;
for(int i = 1; i <= n; ++i){
a[i].clear(); scanf("%d", &k[i]);
a[i].resize(k[i] + 1);
for(int j = 1; j <= k[i]; ++j) scanf("%d", &a[i][j]), las[a[i][j]] = 0, buc[a[i][j]] = 0;
if(!k[i]) P.insert(i);
}
ma[0] = 1; S.insert(0);
for(int i = 1; i <= n; ++i){
ma[i] = ma[i - 1];
for(int j = 1; j <= k[i]; ++j){
++buc[a[i][j]];
if(buc[a[i][j]] > 1) ++cnt;
}
while(cnt){
for(int j = 1; j <= k[ma[i]]; ++j){
--buc[a[ma[i]][j]];
if(buc[a[ma[i]][j]] == 1) --cnt;
}
++ma[i];
}
if(!k[i]) f[i] = 1;
else if(i == 1) f[i] = 0;
else {
int l = ma[i - 1], r = i - 1;
auto it = P.lower_bound(l); auto ti = S.lower_bound(l - 1);
if(it != P.end() && (*it) <= r) f[i] = 1;
else {
for(int j = 1; j <= k[i]; ++j){
int v = a[i][j];
if(ti != S.end() && las[v] >= (*ti) + 1) f[i] = 1;
}
}
}
for(int j = 1; j <= k[i]; ++j) las[a[i][j]] = i;
if(f[i]) S.insert(i);
}
int an = 0, ye = 0;
for(int i = n; i >= ma[n]; --i){
an += k[i]; if(!k[i]) ye = 1;
if(!f[i - 1]) continue;
if(ye) ans = std::max(ans, m);
else ans = std::max(ans, an);
}
printf("%d\n", ans);
return ;
}
int main(){
int T = 1;
scanf("%d", &T);
while(T--) solve();
return 0;
}