P2058题解

Nahia · 2025-01-01 16:32:46 · 题解

思路

以下记 sum_i 为在一天内国籍 i 有抵达的人数，num 为一天内抵达的人的国籍数。

每一艘船上的每一个人到达时，若当前到达的是国籍 x 的乘客，且 sum_x = 0，那么就将 sum_x+1，且 num+1，接着，让这个人的国籍以及到达时间入队，并把队尾指针 +1。

然后，把在一天之前到达的人弹出队列。如果当前的人国籍为 y 且在一天之前到达（即当前时间减去到达时间大于等于 86400），那么 sum_y-1。如果此时 sum_y=0，那么 num-1。然后队头 +1 再处理下一个人。

solution

#include<bits/stdc++.h>
#define ll long long
const int N = 5e5+5;
using namespace std;
ll n,t,k,x,l,r;
ll a[N],f[N],tme[N];
ll num;
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>t>>k;
        while(k--){
            tme[++r]=t;
            cin>>a[r];
            if(!f[a[r]])num++;
            f[a[r]]++;
        }
        while(t-tme[l]>=86400){
            if(!--f[a[l++]])num--;
        }
        cout<<num<<"\n";
    }
    return 0;
}