#P3510. 首都

    ID: 2722 传统题 1000ms 256MiB 尝试: 412 已通过: 120 难度: 8 上传者: 标签>难度分类提高+/省选-树算法树重心离线与分治离线查询子树转区间LCA树上倍增排序与序列处理二分查找数据结构动态开点线段树线段树合并普通并查集位运算异或抵消CF2500

首都

首都

题目描述

X 星球上有 nn 座城市,编号为 11 到 nn。最初每座城市单独组成一个国家,城市间没有公路。

战胜国吞并战败国时,在原来属于两个国家的两座城市间修建一条双向公路。原有公路继续保留。合并后,两国的城市都属于同一个国家。

两座城市间的距离是连接它们的路径所需的最少公路数。每个国家选一座城市为首都,使它到本国所有城市的距离之和最小。如果有多座这样的城市,选编号最小的。

依次处理以下操作。

  • A x y。在城市 xx 和 yy 间修建公路,并合并它们所在的国家。操作前二者属于不同国家。
  • Q x。查询城市 xx 所在国家当前的首都编号。
  • Xor。查询当前所有国家的首都编号按位异或的结果。

输入格式

第一行有两个整数 n,mn,m,分别表示城市数和操作数。接下来 mm 行,每行描述一种操作,格式如上。

输出格式

每遇到 Q 或 Xor 操作,输出一行一个整数,表示该次查询的结果。

样例 #1

10 10
Xor
Q 1
A 10 1
A 1 4
Q 4
Q 10
A 7 6
Xor
Q 7
Xor
11
1
1
1
2
6
2

数据范围

1≤n≤1051\le n\le10^5,1≤m≤2×1051\le m\le2\times10^5,1≤x,y≤n1\le x,y\le n。