#P4320. ShangHai2006 Homework

    ID: 3536 传统题 1000ms 512MiB 尝试: 1394 已通过: 412 难度: 6 上传者: 标签>CF2100提高根号分治倍数枚举离线查询逆向还原操作普通并查集路径压缩按大小合并

ShangHai2006 Homework

题目描述

你需要维护一个集合 SS,支持以下两种操作:

  • A x,插入数值 xx 到集合 SS,保证 xx 插入前未在集合中;
  • B y,询问 SS 集合中 mod y\text{mod }y 的最小值,保证询问时集合不为空。

输入格式

第一行一个整数 nn 表示操作数。

接下来每行一个操作,格式见题目描述。

输出格式

对于每个询问,输出一行一个整数表示答案。

5            
A 3             
A 5 
B 6 
A 9 
B 4 
3
1

数据规模与约定

对于 100%100\% 的数据,1≤n≤1051\leq n\leq 10^5,1≤x.y≤3×1051\leq x.y\leq 3\times 10^5。