【luogu】p2058 海港

题目描述

小K是一个海港的海关工作人员，每天都有许多船只到达海港，船上通常有很多来自不同国家的乘客。

小K对这些到达海港的船只非常感兴趣，他按照时间记录下了到达海港的每一艘船只情况；对于第i艘到达的船，他记录了这艘船到达的时间ti (单位：秒)，船上的乘客数ki，以及每名乘客的国籍 $ x_{i,1}, x_{i,2},…,x_{i,k}$

小K统计了n艘船的信息，希望你帮忙计算出以每一艘船到达时间为止的24小时(24小时=86400秒）内所有乘船到达的乘客来自多少个不同的国家。

形式化地讲，你需要计算n条信息。对于输出的第ii条信息，你需要统计满足$ t_i-86400<t_p le t_i(的船只p，在所有的)x_{p,j}$中，总共有多少个不同的数。

分析

大致思路还是很好想的，

我们开一个数组barrel作为一个桶，barrel[i]表示国籍为i的人有多少个，

每加入一个船，对于船中的人x

如果barrel[x]等于0，则证明又多了一个新国籍的人，

barrel[x]每次都加上1

并且我们找出新增的相距时间超出24的船

把这些船上的乘客在最终答案里减去，

减掉的过程中如果有一个国籍的人被减为0则ans--；

然后就是一个要注意的地方

我们存储这些乘客的信息如果用一个二维数组来存储他所对应的的船和国籍的话空间显然不够用。

体重告诉我们游客总数不会超过3*10^5

所以我们可以对于每一个人分别存储他的国籍和所在船

啊由于人加入的时候都是按时间来有序的，所以也不需要用优先队列什么的吧hmmmmm

Code

#include<iostream>
#include<cstdio>
using namespace std;
int read(){
    int a = 0,f = 0;char p = getchar();
    while(!isdigit(p)){f|=p=='-';p = getchar();}
    while(isdigit(p)){a=(a<<3) + (a<<1) +(p^48);p = getchar();}
    return f?-a:a;
}
int barrel[200001];//记录一个国家的人有几个
int t[200001],k[200001];
struct node{
    int nation,boat;
}person[400001];
int main(){
    int n;
    n = read();
    int now = 1,p = 0,cnt = 0,ans = 0;//记录当前时间到第now个船还在范围内
    //cnt用来统计人数
    int bj = 1;
    while(n--){
        int last = now;//记录好上一次的now到哪了
        t[++p] = read();k[p] = read();
        while(t[p] - t[now] >= 86400){
            now++;
        }//确定好船只的范围 now是合法的第一个
        while(person[bj].boat >= last && person[bj].boat < now){ 
            barrel[person[bj].nation]--;
            if(barrel[person[bj].nation] == 0)ans--;
            bj++;
        }//从上次标记到的
        for(int i = 1;i <= k[p];i++){
            person[++cnt].nation = read();
            person[cnt].boat = p;
            if(barrel[person[cnt].nation] == 0)ans++;
            barrel[person[cnt].nation]++;
        }
        cout<<ans<<endl;
    }
    return 0;
}