| 88 | |
| 89 | // 整体二分，计算每个位置i的first[i]信息 |
| 90 | public static void compute(int ql, int qr, int vl, int vr) { |
| 91 | if (ql > qr) { |
| 92 | return; |
| 93 | } |
| 94 | if (vl == vr) { |
| 95 | for (int i = ql; i <= qr; i++) { |
| 96 | first[i] = vl; |
| 97 | } |
| 98 | return; |
| 99 | } |
| 100 | int mid = (vl + vr) >> 1; |
| 101 | int backup1 = opsize; |
| 102 | boolean bad = false; |
| 103 | for (int i = Math.max(qr + 1, vl); i <= mid; i++) { |
| 104 | union(u[i], v[i]); |
| 105 | union(other(u[i]), other(v[i])); |
| 106 | if (conflict(u[i])) { |
| 107 | bad = true; |
| 108 | break; |
| 109 | } |
| 110 | } |
| 111 | if (bad) { |
| 112 | undo(backup1); |
| 113 | compute(ql, qr, vl, mid); |
| 114 | } else { |
| 115 | int backup2 = opsize; |
| 116 | int split = Math.min(qr, mid); |
| 117 | for (; split >= ql; split--) { |
| 118 | union(u[split], v[split]); |
| 119 | union(other(u[split]), other(v[split])); |
| 120 | if (conflict(u[split])) { |
| 121 | break; |
| 122 | } |
| 123 | } |
| 124 | undo(backup2); |
| 125 | compute(split + 1, qr, mid + 1, vr); |
| 126 | undo(backup1); |
| 127 | for (int i = split + 1; i <= qr && i < vl; i++) { |
| 128 | union(u[i], v[i]); |
| 129 | union(other(u[i]), other(v[i])); |
| 130 | } |
| 131 | compute(ql, split, vl, mid); |
| 132 | } |
| 133 | } |
| 134 | |
| 135 | public static void buildst() { |
| 136 | opsize = 0; |