题目背景
Mike 刚在当地的互联网服务提供商 DNS 找到了一份实习工作。他们知道 Mike 对 IPs 很熟悉,所以请他为他们的客户实现一个支持一些操作的管理系统。其中一些操作是特定于客户端的,而另一些是特定于 DNS(公司) 的。Mike 其实对 IPs 不太了解,所以他向你寻求帮助。
题目描述
IPs 的取值范围是 0 到 109,所有客户端最初都可以使用。有 N 个国家(编号从 0 到 N−1)。每个国家都有自己的 ip 集,形式上可以表示成若干个区间的并集。
有 M 个客户端(编号从 0 到 M−1)需要 Mike 帮助,有 Q 个操作,有以下形式:
1.将一个国家列入所有客户端的黑名单。将一个国家列入黑名单,将阻止该国家及其与其合并的国家对应的所有 ip。
2.将所有客户端的 ip 段 [X,Y] 加入黑名单。
3.为特定客户端将某个国家及其与其合并的国家列入黑名单。
4.将特定客户端的 ip 段 [X,Y] 加入黑名单。
5.为特定客户端将某个国家及其与其合并的国家列入白名单。将一个国家加入白名单,将该国家及其合并国家对应的所有 ip 都加入白名单。请注意,白名单的优先级高于此客户端的任何先前或将来的黑名单。也就是说如果一个 ip 在某个客户端被列入白名单,那么永远不会被适用与接下来以及之前的所有黑名单操作。
6.为特定客户端将 ip 段 [X,Y] 列入白名单。请注意,白名单的优先级高于此客户端的任何先前或将来的黑名单。也就是说如果一个 ip 在某个客户端被列入白名单,那么永远不会被适用与接下来以及之前的所有黑名单操作。
7.国家 X 和 Y 合并在一起。
8.查询某个客户端在 ip 段 [X,Y] 内可以访问多少个 ip ?
输入格式
第一行三个数 N,M,Q。保证 1≤N≤104,1≤M≤10,1≤Q≤105。
接下来 N 行,每行第一个数 Ni 表示第 i 个国家的 ip 集由 Ni 个区间的并集。接下来 2×Ni 个数,表示每个区间,这些数在 0 到 109 之间。保证 ∑Ni≤105。
接下来 Q 行,每行第一个数表示操作的种类,接下来对于每种操作输入对应的参数:
1:countryIdx,保证 0≤countryIdx<N。
2:X,Y,保证 0≤X≤Y≤109。
3:clientIdx,countryIdx,保证 0≤clientIdx<M,0≤countryIdx<N。
4:clientIdx,X,Y,保证 0≤clientIdx<M,0≤X≤Y≤109。
5:clientIdx,countryIdx,保证 0≤clientIdx<M,0≤countryIdx<N。
6:clientIdx,X,Y,保证 0≤clientIdx<M,0≤X≤Y≤109。
7:countryIdx1,countryIdx2,保证 0≤countryIdx1<N,0≤countryIdx2<N。
8:clientIdx,X,Y,保证 0≤clientIdx<M,0≤X≤Y≤109。
输出格式
对于每次询问输出一行表示答案。
2 1 12
1 1 100
1 500 1000
8 0 1 1000
1 0
2 800 900
8 0 1 1000
7 0 1
3 0 0
8 0 1 1000
4 0 200 400
8 0 1 1000
5 0 1
6 0 95 499
8 0 1 1000
1000
799
399
198
1000