大！模！拟！

思路

我们可以用队列来存储每一艘船，以此实现左边删除右边添加的效果。再用数组 $na$ 来存储国籍的人数，并用一个变量 $ans$ 来存储现有多少个不同的国籍。每输入一条船的数据，我们就处理它的信息，更新 $na$ 和 $ans$，并将其加入队列中。然后我们判断当前队首与现在这条船的到达时间是否相差了 $86400s$，如果是的那么将队首出队并继续判断，直到条件不成立。

注意：如果强行开一个 $(3\times 10^5)^2$ 的数组内存肯定会爆，所以我们要使用vector来存储每一艘船上乘客的国籍。

AC Code

实现时可以设一个函数work，用于处理船的信息，这样代码更加易读。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll N=1e5+5,DAY=86400;
ll n,na[N],t[N],ans;
vector<ll> vec[N];
queue<ll> q;
void work(ll x,bool opt){ // opt为1表示删除，0表示添加
    for(auto i=vec[x].begin();i!=vec[x].end();i++){ // 使用迭代器遍历
        na[*i]+=opt?-1:1;
        if(opt&&na[*i]==0)
            ans--;
        else if(!opt&&na[*i]==1)
            ans++;
    }
}
int main(){
    scanf("%lld",&n);
    for(ll i=1,k;i<=n;i++){
        scanf("%lld%lld",&t[i],&k);
        for(ll j=1,x;j<=k;j++)
            scanf("%lld",&x),vec[i].push_back(x);
        q.push(i);
        work(i,0);
        while(!q.empty()&&t[i]-DAY>=t[q.front()]) // 加上!q.empty()防RE
            work(q.front(),1),q.pop();
        printf("%lld\n",ans);
    }
    return 0;
}

AC Code

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int f[N],t[N],k,n,s,ans;
vector<int> v[N];
queue<int> q;
void add(int i,int opt){
	for(int x:v[i]){
		f[x]+=opt;
		if(f[x]==1&&opt==1)
			ans++;
		else if(!f[x]&&opt==-1)
			ans--;
	}
}
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>t[i]>>k;
		for(int j=1;j<=k;j++){
			cin>>s;
			v[i].push_back(s);
		}
		add(i,1);
		q.push(i);
		while(t[q.front()]<=t[i]-86400){
			add(q.front(),-1);
			q.pop();
		}
		cout<<ans<<endl;
	}
}

解题思路

• 用队列存储时间。
• 用cnt数组存储每个国籍有多少人。
• 每次输入时判断：若没有这个国籍的人，就新建一个国籍。
• 如果第一个人到达的时间比当前时间晚，就跳到下一个人。
• 把这个人删掉。如果这个人是他的国籍的唯一一个人，则删除这个国籍。
• 重复前两部操作，直到第一个人到达的时间小于等于当前时间。

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5, T = 86400;
int cnt[N], t[N];
int n, res;
inline void add(int x) {
	res += (++cnt[x] == 1);
}
inline void del(int x) {
	res -= (--cnt[x] == 0);
}
vector<int> a[N];
int main() {
	cin >> n;
	int l = 1;
	for (int r = 1; r <= n; ++r) {
		int k, x;
		cin >> t[r] >> k;
		while (k--) {
			cin >> x;
			add(x);
			a[r].push_back(x);
		}
		while (t[r] - T >= t[l]) {
			for (int i = 0; i < a[l].size(); ++i) {
				del(a[l][i]);
			}
			++l;
		}
		cout << res << '\n';
	}
	return 0;
}