前言

赛时一直RE，思路很清晰，不知道RE哪里。。qwq
赛后开断点发现，map的大小不变，
最后发现是一个if条件写错了，寄。

不知道为什么会想起 银河英雄传说

题意：

初始n个盒子，盒子iii放着编号为iii的小球
进行q次操作

• op1：将y盒子的小球移到x盒子中
• op2：将第k个球，加入到x盒子中
• op3：询问球x在哪个盒子中

思路：

我们看到op1，联想到集合的合并，于时想到并查集的操作
图中绿色的点代表盒子。

1. 经过 多个op1，op1，op1…我们可以用并查集把这些球合并到盒子2
2. 此时，突然有个 op112op_1 \ 1 \ 2op1​ 1 2, 那么我们merge(box[1],box[2])merge(box[1],box[2])merge(box[1],box[2])

merge(int x, int y){int fx = find(x), fy = find(y);p[fy] = fx;//根据题意合并
}

3. 误区：此时突然来个op22op_2 \ 2op2​ 2，

假如新球，连到原来的盒子p[k] = find(box[2]) ,最后会使得新球在盒子1，其实新球在盒子2

因为p[box[2]] == p[box[1]]

做法：

• 对于每个盒子和点都编号
• 每次操作1后，把yyy盒子删除，新建一个y‘y `y‘

box[y] = ++newBox;

What’s more

看了SSRS，好像可以用启发式合并，一开始我也是想用，但后面发现新开点，就可以解决了。

Java

package com.hgs.atcoder.abc.contest279.f;/*** @author youtsuha* @version 1.0* Create by 2022/11/26 19:43*/
import java.util.*;
import java.io.*;
public class Main{static FastScanner cin;static PrintWriter cout;private static void init()throws IOException {cin = new FastScanner(System.in);cout = new PrintWriter(System.out);}private static void close(){cout.close();}static int[] p;static int find(int x){if(x == p[x]) {return p[x];}return p[x] = find(p[x]);}private static void sol()throws IOException {int n = cin.nextInt(), m = cin.nextInt();int tot = n  + m;p = new int[tot*2 + 1];Map curBox = new HashMap<>();Map boxPre = new HashMap<>();int newBox = tot;//[1,tot] balls//[tot+1,tot*2] boxsfor(int i = 1; i <= tot*2; i ++ ) {p[i] = i;if(i > tot && i <= tot + n){newBox++;curBox.put(i - tot,i);boxPre.put(i,i-tot);}else if(i <= n){p[i] = i + tot;}}int k = n;for(int i = 1; i <= m; i ++ ) {int op = cin.nextInt(), x = cin.nextInt();if(op == 1){int y = cin.nextInt();//y-->xint preY = curBox.get(y);p[preY] = p[curBox.get(x)];boxPre.put(++newBox,y);curBox.put(y,newBox);}else if(op == 2){k++;p[k] = curBox.get(x);}else {cout.println(boxPre.get(find(p[x])));}}}public static void main(String[] args) throws IOException {init();sol();close();}
}
class FastScanner {BufferedReader br;StringTokenizer st = new StringTokenizer("");public FastScanner(InputStream s) {br = new BufferedReader(new InputStreamReader(s));}public FastScanner(String s) throws FileNotFoundException {br = new BufferedReader(new FileReader(new File(s)));}public String next() throws IOException {while (!st.hasMoreTokens()){try {st = new StringTokenizer(br.readLine());} catch (IOException e) { e.printStackTrace(); }}return st.nextToken();}public int nextInt() throws IOException {return Integer.parseInt(next());}public long nextLong() throws IOException {return Long.parseLong(next());}public double nextDouble() throws IOException {return Double.parseDouble(next());}
}