| 95 | } |
| 96 | int ans[N]; |
| 97 | void query(int n, int b, int e) { |
| 98 | if(b > e) return; |
| 99 | int prevsz = d.st.size(); |
| 100 | ///add edges which were alive in this range |
| 101 | for(auto p : alive[n]) d.unite(p.first, p.second); |
| 102 | if(b == e) { |
| 103 | ans[b] = d.comp; |
| 104 | d.backtrack(d.st.size() - prevsz); |
| 105 | return; |
| 106 | } |
| 107 | int l = 2 * n, r = l + 1, mid = b + e >> 1; |
| 108 | query(l, b, mid); |
| 109 | query(r, mid + 1, e); |
| 110 | d.backtrack(d.st.size() - prevsz); |
| 111 | } |
| 112 | struct HASH { |
| 113 | size_t operator()(const pair<int, int>&x)const { |
| 114 | return hash<long long>()(((long long)x.first) ^ (((long long)x.second) << 32)); |