#P3578. GTY的人类基因组计划2

    ID: 2779 传统题 1000ms 128MiB 尝试: 591 已通过: 190 难度: 6 上传者: 标签>难度分类提高随机化与近似随机哈希位运算异或抵消数据结构有序集合构造与建模势能分析CF2100Byorzpzmaimeng

GTY的人类基因组计划2

GTY 的人类基因组计划 2

题目描述

有 nn 个人和 mm 个房间,所有人最初都在 11 号房间。GTY 可以让某个人搬到指定房间,也可以让一段连续编号的房间同时进行实验。

一个房间实验时,把其中所有人的编号看作一个集合。若这一集合从未进行过实验,本次获得的点数等于集合内的人数;否则获得 00 点。是否实验过只与集合有关,与在哪个房间无关。不同的集合即使有共同成员,仍分别判断。

请对每次实验指令,求参与实验的所有房间获得的点数之和。

输入格式

第一行三个整数 n,m,qn,m,q,分别表示人数、房间数和操作数。人从 11 到 nn 编号,房间从 11 到 mm 编号。接下来 qq 行,每行一个操作:

  • C i j:把第 ii 个人移至第 jj 个房间。
  • W l r:让编号从 ll 到 rr 的房间做实验,包括两端。

输出格式

对于每条 W 指令,输出一行一个整数,为此次获得的实验信息点数。

样例

3 5 7
C 1 2
C 2 2
W 1 2
C 3 2
W 1 2
C 3 3
W 1 3
3
3
0

数据规模与约定

对于 100%100\% 的数据满足 n,m,q≤105n,m,q\le 10^5。

善用 STL。