模拟(40pts)

• 有40%的数据是时间是小于等于86400，也就是我们只需要处理不同的国家的数目即可。

#include<bits/stdc++.h>
using namespace std;
const int N=1000010;
int st[N];
int main()
{
    int n;
    cin>>n;
    while(n--)
    {
        int t,c;
        cin>>t>>c;
        for(int i=1;i<=c;i++) //枚举所有人
        {
            int x;
            cin>>x;
            st[x]++; //标记当前人出现过
        }  
        int cnt=0;
        for(int i=1;i<=N;i++) //枚举所有的国籍
        {
            if(st[i])
            {
                cnt++;
            }
        }
        cout<<cnt<<endl;
    }
    return 0;
}

模拟($O \sum k_i $100pts)

• 每次来船，先统计，有新的国籍就增加，然后删除窗口外的人，如果删除了没有人了，就减少一个国籍的人。

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int n;
int t[N];
vector<int> q[N]; //储存每个时刻的人
int s[N]; //储存每个国籍的出现的人的数量
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=0;i<n;i++)
    {
        cin>>t[i]; //获取第i个船来的时刻
        int cnt;
        cin>>cnt; //获取第i个船来的人数
        while(cnt--)
        {
            int x;
            cin>>x;
            q[i].push_back(x); //储存第i个时刻来的人是属于哪个国家的
        }
    }
    for(int i=0,j=0,c=0;i<n;i++) //i表示当前时刻，j表示当前窗口的第一个时刻
    {
        for(int x:q[i]) //添加每个来的人
        {
           s[x]++;
           if(s[x]==1) c++; //新增加了一个国家
        }
        while(t[i]-t[j]>=86400) //判断是否超过一天
        {
            for(int x:q[j]) //移除超时的人
            {
                s[x]--;
                if(s[x]==0) c--; //当前国家已经没有人了
            }
            j++;
        }
        cout<<c<<endl;
    }
    return 0;
}