https://www.cnblogs.com/violet-acmer/p/9859003.html
这次比赛，上来还是死抠第一题，用了一个半小时才 AC，还是太菜了..................
题意：
一共有 n 艘船，每艘船都有一个到港时间，每艘船上有 k 个人，这 k 个人可能来自多个不同的国家；
求以当前船只为终了时间，在这之前的 24 小时内，到港的所有船只中所承载的乘客来自多少个国家？
题解：
相关变量解释：
arrive[maxn]........................................arrive[ i ] : 第 i 艘船到港的时间
affect[maxn].........................................affect[ i ] : i 国籍为所影响的范围，但不包括其本身
vector<int >ship[maxn].........................ship[ i ] : 第 i 艘船上所承载的乘客国籍信息
diff[maxn].............................................差分数组
因为 k1+k2+.......+k2 <= 3e5，所以用vector存不会超内存。
1.去重
因每艘船的 k 个人可能有来自同一国家的乘客，所以先去一下重
sort(ship[i].begin(),ship[i].end());
ship[i].erase(unique(ship[i].begin(),ship[i].end()),ship[i].end());
2.找到每艘船的乘客所能影响的最大范围
这是什么意思呢？
例如，第一艘船去重后，乘客分别来自 1,2,4 国家，由于所要求得是以当前船只为终了时间，在这之前的 24 小时内，
到港的所有船只中所承载的乘客来自多少个国家；
换句话说，当前船只的乘客只能影响这之后的 24 小时内到达的船只（不包含第 24 小时到达的船只）。
所以第一艘船的 1 乘客的影响范围为[1,1+86400)，此时，记 affect[1]=1+86400，但 1 所影响的范围不包括 affect[1]本身
同理，第 2,4 乘客的影响范围也为[1,1+86400)
当来到第二艘船的时候，去重后，乘客分别来自 2,3 国家，而当前船只到港时间为 2 ，affect[2]=1+86400 > 2，所以受之前
船只的影响，国籍为 2 的乘客并不会对[2,1+86400)造成影响，而当前的 2 乘客可以影响的范围为 [2,2+86400)，所以需要
在之前的范围[1,1+86400)上加上范围[1+86400,2+86400)，即加上[affect[2], 2+86400)，并将affect[2]更新为2+86400。
3.求解
但要如何记录以当前船只为终了时间的前 24 小时内的不同国家的乘客人数呢？
由题干可知，t <= 1e9，难不成要开个 1e9 大的数组，显然是不可行的，那该怎么办呢？
看题干，保证所输入的 t 是递增的，而 n <= 1e5，所以可以将affect[ i ]中乘客 i 的影响范围由之前的时间区间变为船只编号，如何变呢？
还是以样例为例：
一共有 3 艘船，每艘船的到港时间分别为 1,2,10
第一艘船的乘客可以影响的时间范围为[1,1+86400)，也就是说，只要到港时间在[1,1+86400)范围内的船只，都可以影响到，而后两艘船
的到港时间都在这个时间范围内，所以将 affect[1]=affect[2]=affect[4]=4，意思是第一艘船的第 1,2,4乘客可以影响到前三艘船。
来到第二艘船，其乘客国籍为 2,3，但affect[2]=4 > 2，说明在这之前的 24 小时内，有船只载有 2 国家的乘客，所以当前船只的 2 乘客能
影响的范围变为[affect[2],end)，end 指的是到港时间 >= 2+86400 最近的一艘船编号，易得 end = 4。
其余的船只同理。
因为每艘船只的到港时间是递增的，所以每次查找可以使用二分。
而第 i 艘船上的每个乘客的影响范围可以用树状数组或线段树来维护；
而我选择了一个比较方便的差分数组，何为差分数组，详情请看http://www.cnblogs.com/widsom/p/7750656.html
AC代码：
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define lowbit(x) (x&(-x))
#define mem(a,b) memset(a,b,sizeof a)
const int maxn=1e5+; int n;
int arrive[maxn];
int affect[maxn];
vector<int >ship[maxn];
int diff[maxn];
void Solve()
{
mem(affect,);
mem(diff,);
for(int i=;i <= n;++i)
{
//t : 到港时间 >= arrive[i]+86400 的最近的一艘船的编号
int t=lower_bound(arrive+i,arrive+n+,arrive[i]+)-arrive;
for(int j=;j < ship[i].size();++j)
{
int native=ship[i][j];
if(affect[native] < i)//判断一下affect[native]影响的范围是否包含当前船只 i
affect[native]=i;//如果不包含，则当前乘客的影响范围从当前船只开始
diff[affect[native]]++;//当前乘客的影响范围为 [affect[native],t)
diff[t]--;
affect[native]=t;//更新affect[native]
}
}
for(int i=;i <= n;++i)
{
diff[i] += diff[i-];//一遍前缀和为元素本身，也就是以当前船只为终了时间的前24小时内的来自不同国家的个数
printf("%d\n",diff[i]);
}
}
int main()
{
scanf("%d",&n);
for(int i=;i <= n;++i)
{
int t,k;
scanf("%d%d",&t,&k);
arrive[i]=t;
for(int j=;j <= k;++j)
{
int native;
scanf("%d",&native);
ship[i].pb(native);
}
sort(ship[i].begin(),ship[i].end());
ship[i].erase(unique(ship[i].begin(),ship[i].end()),ship[i].end());
}
Solve();
}
/**
5
1 4 4 1 2 2
2 2 2 3
10 1 3
100000 5 1 2 3 4 5
100001 5 1 2 3 4 6
**/