CF1819D Misha and Apples 题解

complete_binary_tree · 2024-03-30 16:41:00 · 题解

显然，我们要让最后一次清空最提前。

那么我们设 f_i 为 S_i 之前最后一次被清空最提前的位置。

然后我们要满足以下几个条件：

• 最后一次清空以后，也就是 [f_i,i) 中的元素都不能和 S_i 重复。

• 位置 f_i 是可以被清空的。

前面那个条件很容易满足，预处理一下不能被清空的最后一位在哪里就行了。（记作 mx_i）

后面那个条件，我们可以再设一个 g_i，为到 i 能否清空。

• 首先，f_i 之前肯定是要被清空的。也就是说，我们只需要看 (f_i, i] 是否能删除就行了。

  • 如果这段中有 k_i = 0（能自定义）的段，那么肯定能删除。（这个预处理一下就能 O(1) 求了）

  • 否则，要看 mx_i 在不在 (f_i, i) 里面，如果在也能删除。

  • 如果不在，那么也就删除不了了。

那么 f_i 的转移就可以是：

• 首先，f_i 肯定大于等于 f_{i - 1}。因为 f_{i - 1} 之前的东西肯定都被清空掉了。所以 f_i 初始值为 f_{i - 1}。

• 然后，mx_i 肯定不能在 f_i 到 i 之间。否则 i 就会被清除了。那么 f_i 自增直到 \ge mx_i。（当然直接取 \max 应该也没问题）

• 还有，g_{f_i} 要为 1。所以直接往后找找到一个 1 就行了。

然后我们可以先更新 g_i，再更新 f_{i+1}。

最后，统计答案的时候，如果 (f_n, n] 中有空集，那么直接输出 m，否则只要模拟一下即可。

由于 \sum m 没有保证，所以需要注意一下清空的复杂度。

代码：

#include<bits/stdc++.h>
using namespace std;

const int N = 2e5 + 5;

int t, k[N], n, m, lst[N], mx[N], g[N], lstcan[N];
vector<int> s[N];
queue<int> q;

int main(){
    scanf( "%d", &t );
    while( t-- ){
        scanf( "%d%d", &n, &m );
        for( int i = 1; i <= n; ++i ){
            mx[i] = 0;
            scanf( "%d", &k[i] );
            s[i].resize( k[i] + 1 );
            if( k[i] == 0 ) lstcan[i] = i; else lstcan[i] = lstcan[i - 1];
            for( int j = 1; j <= k[i]; ++j ){ scanf( "%d", &s[i][j] ); mx[i] = max( lst[s[i][j]], mx[i] ); lst[s[i][j]] = i; q.push( s[i][j] ); }
        }
        for( int i = 1; i <= n + 1; ++i ) g[i] = 0;
        g[0] = 1;int f = 0; //其实 f 没必要开成数组，现场计算现场用即可。
        for( int i = 1; i <= n; ++i ){
            if( lstcan[i] > f || mx[i] > f ) g[i] = 1; else g[i] = 0;
            while( g[f] == 0 || f < mx[i] ) ++f;
        }
        int ans = 0;
        if( lstcan[n] > f ) printf("%d\n", m);
        else{ for( int i = f + 1; i <= n; ++i ) ans += k[i]; printf("%d\n", ans); }
        while( !q.empty() ) lst[q.front()] = 0, q.pop(); //注意清空的时间复杂度
    }
    return 0;
}