Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.io.OutputStream;
- import java.io.IOException;
- import java.io.InputStream;
- import java.io.OutputStream;
- import java.io.PrintWriter;
- import java.io.BufferedWriter;
- import java.util.InputMismatchException;
- import java.io.IOException;
- import java.util.ArrayList;
- import java.util.List;
- import java.io.Writer;
- import java.io.OutputStreamWriter;
- import java.io.InputStream;
- /**
- * Built using CHelper plug-in
- * Actual solution is at the top
- *
- * @author Roy
- */
- public class Main {
- public static void main(String[] args) {
- InputStream inputStream = System.in;
- OutputStream outputStream = System.out;
- InputReader in = new InputReader(inputStream);
- OutputWriter out = new OutputWriter(outputStream);
- BuildingAResearchAndDevelopmentCenter solver = new BuildingAResearchAndDevelopmentCenter();
- solver.solve(1, in, out);
- out.close();
- }
- static class BuildingAResearchAndDevelopmentCenter {
- public void solve(int testNumber, InputReader in, OutputWriter out) {
- int n = in.readInteger();
- int q = in.readInteger();
- int[] seniority = new int[n];
- for (int i = 0; i < n; i++) {
- int id = in.readInteger();
- seniority[id] = n - i;
- }
- DisjointSetUnion dsu = new DisjointSetUnion(n, seniority);
- for (int i = 0; i < q; i++) {
- int query = in.readInteger();
- if (query == 1) {
- int id1 = in.readInteger();
- int id2 = in.readInteger();
- dsu.union(id1, id2);
- } else if (query == 2) {
- int id = in.readInteger();
- seniority[id]++;
- int parent = dsu.find(id);
- int seniorId = dsu.getSenior(parent);
- if (seniority[id] > seniority[seniorId]) dsu.setSenior(parent, id);
- else if (seniority[seniorId] == seniority[seniorId]) dsu.setSenior(parent, Math.max(id, seniorId));
- } else {
- out.printLine(dsu.getSenior(in.readInteger()));
- }
- }
- }
- }
- static class DisjointSetUnion {
- int[] senior;
- int[] seniority;
- private List<Integer> link;
- private List<Integer> size;
- private void init(int nodes) {
- for (int i = 0; i < nodes; i++) {
- this.senior[i] = i;
- link.add(i);
- size.add(1);
- }
- }
- public DisjointSetUnion(int nodes, int[] seniority) {
- link = new ArrayList<>();
- size = new ArrayList<>();
- senior = new int[nodes];
- this.seniority = seniority;
- this.init(nodes);
- }
- public int find(int node) {
- if (node == link.get(node)) return node;
- link.set(node, find(link.get(node)));
- return link.get(node);
- }
- public int getSenior(int id) {
- return senior[id] = senior[find(id)];
- }
- public void setSenior(int id, int who) {
- this.senior[id] = who;
- }
- public void union(int firstNode, int secondNode) {
- firstNode = find(firstNode);
- secondNode = find(secondNode);
- if (size.get(firstNode) < size.get(secondNode))
- firstNode = Swap.between(secondNode, secondNode = firstNode);
- size.set(firstNode, size.get(firstNode) + size.get(secondNode));
- link.set(secondNode, firstNode);
- int sn;
- if (seniority[firstNode] > seniority[secondNode]) sn = firstNode;
- else if (seniority[firstNode] == seniority[secondNode]) {
- sn = Math.max(firstNode, secondNode);
- } else sn = secondNode;
- senior[firstNode] = senior[secondNode] = sn;
- }
- }
- static class InputReader {
- private int curChar;
- private int numChars;
- private InputReader.SpaceCharFilter filter;
- private final InputStream stream;
- private final byte[] buf = new byte[1024];
- public InputReader(InputStream stream) {
- this.stream = stream;
- }
- private long readWholeNumber(int c) {
- long res = 0;
- do {
- if (c < '0' || c > '9') {
- throw new InputMismatchException();
- }
- res *= 10;
- res += c - '0';
- c = read();
- } while (!isSpaceChar(c));
- return res;
- }
- public int read() {
- if (numChars == -1) {
- throw new InputMismatchException();
- }
- if (curChar >= numChars) {
- curChar = 0;
- try {
- numChars = stream.read(buf);
- } catch (IOException e) {
- throw new InputMismatchException();
- }
- if (numChars <= 0) {
- return -1;
- }
- }
- return buf[curChar++];
- }
- public int readInteger() {
- int c = read();
- while (isSpaceChar(c)) {
- c = read();
- }
- int sgn = 1;
- if (c == '-') {
- sgn = -1;
- c = read();
- }
- int res = (int) readWholeNumber(c);
- return res * sgn;
- }
- public boolean isSpaceChar(int c) {
- if (filter != null) {
- return filter.isSpaceChar(c);
- }
- return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
- }
- public interface SpaceCharFilter {
- boolean isSpaceChar(int ch);
- }
- }
- static class Swap {
- public static <T> T between(T a, T b) {
- return a;
- }
- }
- static class OutputWriter {
- private final PrintWriter writer;
- public OutputWriter(OutputStream outputStream) {
- writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream)));
- }
- public OutputWriter(Writer writer) {
- this.writer = new PrintWriter(writer);
- }
- public void print(Object... objects) {
- for (int i = 0; i < objects.length; i++) {
- if (i != 0) {
- writer.print(' ');
- }
- writer.print(objects[i]);
- }
- }
- public void printLine(Object... objects) {
- this.print(objects);
- writer.println();
- }
- public void close() {
- writer.flush();
- writer.close();
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement