[AGM 2023 资格赛] IPs

Luogu

IDLGP9279

Time10000ms

Memory2048MB

DifficultyP6

2023O2优化AGM

IPs 的取值范围是 $0$ 到 $10^9$，所有客户端最初都可以使用。有 $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 ？ ## Input 第一行三个数 $N,M,Q$。保证 $1\leq N\leq 10^4,1\leq M\leq 10,1\leq Q\leq 10^5$。接下来 $N$ 行，每行第一个数 $N_i$ 表示第 $i$ 个国家的 ip 集由 $N_i$ 个区间的并集。接下来 $2\times N_i$ 个数，表示每个区间，这些数在 $0$ 到 $10^9$ 之间。保证 $\sum N_i\leq 10^5$。接下来 $Q$ 行，每行第一个数表示操作的种类，接下来对于每种操作输入对应的参数： 1：$countryIdx$，保证 $0≤countryIdx<N$。 2：$X, Y$，保证 $0≤X≤Y≤10^9$。 3：$clientIdx, countryIdx$，保证 $0≤clientIdx<M, 0≤countryIdx<N$。 4：$clientIdx,X, Y$，保证 $0≤clientIdx<M, 0≤X≤Y≤10^9$。 5：$clientIdx, countryIdx$，保证 $0≤clientIdx<M, 0≤countryIdx<N$。 6：$clientIdx,X, Y$，保证 $0≤clientIdx<M, 0≤X≤Y≤10^9$。 7：$countryIdx1, countryIdx2$，保证 $0≤countryIdx1<N, 0≤countryIdx2<N$。 8：$clientIdx,X,Y$，保证 $0≤clientIdx<M, 0≤X≤Y≤10^9$。 ## Output 对于每次询问输出一行表示答案。 [samples] ## Background Mike 刚在当地的互联网服务提供商 DNS 找到了一份实习工作。他们知道 Mike 对 IPs 很熟悉，所以请他为他们的客户实现一个支持一些操作的管理系统。其中一些操作是特定于客户端的，而另一些是特定于 DNS(公司) 的。Mike 其实对 IPs 不太了解，所以他向你寻求帮助。

Samples

Input #1

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

Output #1

API Response (JSON)

{
  "problem": {
    "name": "[AGM 2023 资格赛] IPs",
    "description": {
      "content": "IPs 的取值范围是 $0$ 到 $10^9$，所有客户端最初都可以使用。有 $N$ 个国家（编号从 $0$ 到 $N−1$）。每个国家都有自己的 ip 集，形式上可以表示成若干个区间的并集。 有 $M$ 个客户端（编号从 $0$ 到 $M−1$）需要 Mike 帮助，有 $Q$ 个操作，有以下形式: 1.将一个国家列入所有客户端的黑名单。将一个国家列入黑名单，将阻止该国家及其与其合并的国家对",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 10000,
      "memory_limit": 2097152
    },
    "difficulty": {
      "LuoguStyle": "P6"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP9279"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "IPs 的取值范围是 $0$ 到 $10^9$，所有客户端最初都可以使用。有 $N$ 个国家（编号从 $0$ 到 $N−1$）。每个国家都有自己的 ip 集，形式上可以表示成若干个区间的并集。\n\n有 $M$ 个客户端（编号从 $0$ 到 $M−1$）需要 Mike 帮助，有 $Q$ 个操作，有以下形式:\n\n1.将一个国家列入所有客户端的黑名单。将一个国家列入黑名单，将阻止该国家及其与其合并的国家对...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments