#P9279. [AGM 2023 资格赛] IPs

[AGM 2023 资格赛] IPs

题目背景

Mike 刚在当地的互联网服务提供商 DNS 找到了一份实习工作。他们知道 Mike 对 IPs 很熟悉,所以请他为他们的客户实现一个支持一些操作的管理系统。其中一些操作是特定于客户端的,而另一些是特定于 DNS(公司) 的。Mike 其实对 IPs 不太了解,所以他向你寻求帮助。

题目描述

IPs 的取值范围是 0010910^9,所有客户端最初都可以使用。有 NN 个国家(编号从 00N1N−1)。每个国家都有自己的 ip 集,形式上可以表示成若干个区间的并集。

MM 个客户端(编号从 00M1M−1)需要 Mike 帮助,有 QQ 个操作,有以下形式:

1.将一个国家列入所有客户端的黑名单。将一个国家列入黑名单,将阻止该国家及其与其合并的国家对应的所有 ip。

2.将所有客户端的 ip 段 [X,Y][X,Y] 加入黑名单。

3.为特定客户端将某个国家及其与其合并的国家列入黑名单。

4.将特定客户端的 ip 段 [X,Y][X,Y] 加入黑名单。

5.为特定客户端将某个国家及其与其合并的国家列入白名单。将一个国家加入白名单,将该国家及其合并国家对应的所有 ip 都加入白名单。请注意,白名单的优先级高于此客户端的任何先前或将来的黑名单。也就是说如果一个 ip 在某个客户端被列入白名单,那么永远不会被适用与接下来以及之前的所有黑名单操作。

6.为特定客户端将 ip 段 [X,Y][X,Y] 列入白名单。请注意,白名单的优先级高于此客户端的任何先前或将来的黑名单。也就是说如果一个 ip 在某个客户端被列入白名单,那么永远不会被适用与接下来以及之前的所有黑名单操作。

7.国家 XXYY 合并在一起。

8.查询某个客户端在 ip 段 [X,Y][X, Y] 内可以访问多少个 ip ?

输入格式

第一行三个数 N,M,QN,M,Q。保证 1N104,1M10,1Q1051\leq N\leq 10^4,1\leq M\leq 10,1\leq Q\leq 10^5

接下来 NN 行,每行第一个数 NiN_i 表示第 ii 个国家的 ip 集由 NiN_i 个区间的并集。接下来 2×Ni2\times N_i 个数,表示每个区间,这些数在 0010910^9 之间。保证 Ni105\sum N_i\leq 10^5

接下来 QQ 行,每行第一个数表示操作的种类,接下来对于每种操作输入对应的参数:

1:countryIdxcountryIdx,保证 0countryIdx<N0≤countryIdx<N

2:X,YX, Y,保证 0XY1090≤X≤Y≤10^9

3:clientIdx,countryIdxclientIdx, countryIdx,保证 0clientIdx<M,0countryIdx<N0≤clientIdx<M, 0≤countryIdx<N

4:clientIdx,X,YclientIdx,X, Y,保证 0clientIdx<M,0XY1090≤clientIdx<M, 0≤X≤Y≤10^9

5:clientIdx,countryIdxclientIdx, countryIdx,保证 0clientIdx<M,0countryIdx<N0≤clientIdx<M, 0≤countryIdx<N

6:clientIdx,X,YclientIdx,X, Y,保证 0clientIdx<M,0XY1090≤clientIdx<M, 0≤X≤Y≤10^9

7:countryIdx1,countryIdx2countryIdx1, countryIdx2,保证 0countryIdx1<N,0countryIdx2<N0≤countryIdx1<N, 0≤countryIdx2<N

8:clientIdx,X,YclientIdx,X,Y,保证 0clientIdx<M,0XY1090≤clientIdx<M, 0≤X≤Y≤10^9

输出格式

对于每次询问输出一行表示答案。

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