题解：P17853 [LBA-OI R6 A] Su通ki信yu题ri

· · 题解

设 Bob 收到的集合为 R。R = S \cup \{x\}。

注意到，x\in R 合法当且仅当 x 为 \overline{S} 中第 m 小的数，也就是 \overline{S} 中比 x 小的数恰有 m - 1 个。

因为 R = S \cup \{x\}，所以「\overline{S} 中比 x 小的数的个数」与「\overline{R} 中比 x 小的数的个数」相等。

所以可以预处理一下，对于数 k，有多少个数属于 \overline{R} 且小于 k。再遍历一遍 R，观察每个 x\in R 是否合法。因为 R 按升序给出，所以遍历得来的答案也是升序的。时间复杂度 O\left(\sum n\right)。 ::::info[code]

#include<bits/stdc++.h>
using namespace std;
const int maxn=2e6+10;
int T,n,m;
bool vis[maxn];
int sum[maxn],s[1000010];
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>T;
    while(T--){
        cin>>n>>m;
        for(int i=1;i<=n;i++)
            vis[i]=1;
        for(int i=1;i<=m;i++){
            cin>>s[i];
            vis[s[i]]=0;
        }
        for(int i=1;i<=n;i++)
            sum[i]=sum[i-1]+vis[i];
        int cnt=0;
        vector<int> ans;
        for(int i=1;i<=m;i++){
            int pos=s[i];
            int tot=sum[pos-1];
            if(tot==m-1){
                ans.push_back(pos);
                cnt++;
            }
        }
        cout<<cnt<<'\n';
        for(int i=0;i<cnt;i++)
            cout<<ans[i]<<' ';
        cout<<'\n';
    }
    return 0;
}

::::