【数据结构】线段树复杂应用

星际网络2

随着星际网络的进一步建设和规模的增大，一个新的问题出现在网络工程师面前——地址空间不够用了！

原来，星际网络采用了传统的 IPv6 协议，虽然有 $2^{128}$ 级别的可用地址数量，但面对广袤无垠的宇宙和爆炸式增长的网络用户数，如此庞大的地址空间也面临了用尽的那一天。

新的通信协议的研发工作交给了著名的网络科技圣地——西西艾弗星。

最终，经过 $2333$ 年的不懈努力，西西艾弗星的工程师们设计出了一种新的协议——“西西艾弗IP协议”，又称 IPxxaf。

在 IPxxaf 协议中，一个地址由 $n$ 位二进制位组成，其中 $n$ 是 $16$ 的倍数。

日常表示一个地址时，采用类似 IPv6 协议的十六进制表示法，每 $4$ 位用 : 隔开。

如 $n=32$ 时，地址为 2a00:0001，即表示一个二进制为 0010 1010 0000 0000 0000 0000 0000 0001 的地址。

注意不会出现 IPv6 中省略每组的前导 $0$ 或用 :: 省略一段 $0$ 的情况。

为方便起见，记 $num(s)$ 为地址 $s$ 按高位在前、低位在后组成的 $n$ 位二进制数，称一段“连续的地址“为 $num(s)$ 成一段连续区间的一系列地址。

西西艾弗星的网络管理员负责地址的分配与管理。

最开始，整个地址空间都是未分配的。

用户可以随时向管理员申请一些地址：

1 id l r：表示用户 $id$ 申请地址在 $l\sim r$ 范围内（包含 $l$ 和 $r$，下同）的一段连续地址块。

在地址申请操作中，管理员需要先检查地址是否可用。

如果用户申请的地址全部未被分配，则检查通过；若地址中存在已经分配给其他用户的地址，则检查失败。

但有一种特殊情况：申请的地址中没有已经分配给其他用户的地址，但含有一些先前已分配给该用户本人的地址。

此时可以认为检查通过，但若申请的地址先前已全部分配给该用户则检查失败。

如果上述检查通过，则管理员向用户返回 YES，并将申请的地址分配给该用户；若不通过，则向用户返回 NO，同时不改变现有的地址分配。

网络管理员要定期检查地址的分配情况，具体而言有如下两种操作：

2 s：检查地址 $s$ 被分配给了哪个用户。若未被分配，则结果为 $0$。

3 l r：检查 $l\sim r$ 范围内的所有地址是否完整地分配给了某个用户。若是，回答该用户的编号；若否，回答 $0$。

在整个网络的运行过程中，共出现了 $q$ 次申请地址和检查地址分配的操作。

作为西西艾弗星的一名重要的网络技术顾问，你要帮网络管理员依次处理每个操作，并回答相应的结果。

输入格式

第一行，$2$ 个正整数 $n,q$。

接下来 $q$ 行，每行一个操作，格式如上所述，其中的 $id$ 为正整数，$l,r,s$ 均为 IPxxaf 地址串，其中十六进制均用数字和小写字母表示。

输出格式

输出 $q$ 行，每行一个非负整数或字符串，表示此次操作的结果。

其中，对于操作 $1$，输出 YES 或 NO；对于操作 $2,3$，输出一个非负整数。

数据范围

对于所有数据，$n\le 512$，$q\le 5\times 10^4$，$n$ 为 $16$ 的倍数，$id\le q$，对于操作 $1,3$ 保证 $num(l)\le num(r)$。

测试点编号

$n\le$

$q\le$

特殊性质

$1\sim 4$

$16$

$200$

无

$5\sim 6$

$64$

$200$

无

$7\sim 9$

$512$

$200$

无

$10\sim 11$

$16$

$20000$

无

$12\sim 13$

$64$

$50000$

无

$14\sim 16$

$512$

$50000$

所有操作 $1$ 的 $id$ 互不相同

$17\sim 20$

$512$

$50000$

无

输入样例：

32 12
1 1 0001:8000 0001:ffff
2 0001:a000
3 0001:c000 0001:ffff
1 2 0000:0000 000f:ffff
2 0000:1000
1 1 0001:8000 0001:8fff
1 2 0000:0000 0000:ffff
2 0000:1000
1 1 0002:8000 0002:ffff
3 0001:8000 0002:ffff
1 1 0001:c000 0003:ffff
3 0001:8000 0002:ffff

输出样例：

YES
1
1
NO
0
NO
YES
2
YES
0
YES
1

样例解释

第 $4$ 个操作时，由于用户 $2$ 申请的部分地址已被分配给用户 $1$，因此申请不通过；

第 $6$ 个操作时，由于用户 $1$ 申请的全部地址已被分配给用户 $1$，因此申请不通过；

第 $11$ 个操作时，用户 $1$ 申请的部分地址已被分配给用户 $1$，其余地址尚未被分配，申请通过；

星际旅行

PS无线版

线段树+离散化

逆序对
point
星际旅行（就是那个xs[r]-xs[l-1]）
一篇很好的题解