| 74 | } |
| 75 | |
| 76 | public static int remove(int i) { |
| 77 | int h = find(i); |
| 78 | father[ls[i]] = ls[i]; |
| 79 | father[rs[i]] = rs[i]; |
| 80 | int s = merge(ls[i], rs[i]); |
| 81 | int f = up[i]; |
| 82 | father[i] = s; |
| 83 | up[s] = f; |
| 84 | if (h != i) { |
| 85 | father[s] = h; |
| 86 | if (ls[f] == i) { |
| 87 | ls[f] = s; |
| 88 | } else { |
| 89 | rs[f] = s; |
| 90 | } |
| 91 | for (int d = dist[s], tmp; dist[f] > d + 1; f = up[f], d++) { |
| 92 | dist[f] = d + 1; |
| 93 | if (dist[ls[f]] < dist[rs[f]]) { |
| 94 | tmp = ls[f]; |
| 95 | ls[f] = rs[f]; |
| 96 | rs[f] = tmp; |
| 97 | } |
| 98 | } |
| 99 | } |
| 100 | up[i] = ls[i] = rs[i] = dist[i] = 0; |
| 101 | return father[s]; |
| 102 | } |
| 103 | |
| 104 | public static void main(String[] args) throws Exception { |
| 105 | FastReader in = new FastReader(System.in); |