| 117 | } |
| 118 | |
| 119 | public static void compute(int l, int r) { |
| 120 | // 重要剪枝 |
| 121 | // 保证每条查询只在一个边的序列块中处理 |
| 122 | cursiz = 0; |
| 123 | for (int i = 1; i <= q; i++) { |
| 124 | if (ea[edge[l]] <= qa[query[i]] && (r + 1 > m || qa[query[i]] < ea[edge[r + 1]])) { |
| 125 | cur[++cursiz] = query[i]; |
| 126 | } |
| 127 | } |
| 128 | if (cursiz > 0) { |
| 129 | // 重建并查集，目前没有任何连通性 |
| 130 | build(); |
| 131 | // 本题直接排序能通过，就不写归并了 |
| 132 | sort(edge, eb, 1, l - 1); |
| 133 | for (int i = 1, j = 1; i <= cursiz; i++) { |
| 134 | while (j < l && eb[edge[j]] <= qb[cur[i]]) { |
| 135 | union(eu[edge[j]], ev[edge[j]], ea[edge[j]], eb[edge[j]]); |
| 136 | j++; |
| 137 | } |
| 138 | opsize = 0; |
| 139 | for (int k = l; k <= r; k++) { |
| 140 | if (ea[edge[k]] <= qa[cur[i]] && eb[edge[k]] <= qb[cur[i]]) { |
| 141 | union(eu[edge[k]], ev[edge[k]], ea[edge[k]], eb[edge[k]]); |
| 142 | } |
| 143 | } |
| 144 | ans[cur[i]] = check(qu[cur[i]], qv[cur[i]], qa[cur[i]], qb[cur[i]]); |
| 145 | undo(); |
| 146 | } |
| 147 | } |
| 148 | } |
| 149 | |
| 150 | public static void prepare() { |
| 151 | int log2n = 0; |