| 140 | } |
| 141 | |
| 142 | SqrtTree(const vector<SqrtTreeItem>& a) |
| 143 | : n((int)a.size()), llg(log2Up(n)), v(a), clz(1 << llg), onLayer(llg + 1) { |
| 144 | clz[0] = 0; |
| 145 | for (int i = 1; i < (int)clz.size(); i++) { |
| 146 | clz[i] = clz[i >> 1] + 1; |
| 147 | } |
| 148 | int tllg = llg; |
| 149 | while (tllg > 1) { |
| 150 | onLayer[tllg] = (int)layers.size(); |
| 151 | layers.push_back(tllg); |
| 152 | tllg = (tllg + 1) >> 1; |
| 153 | } |
| 154 | for (int i = llg - 1; i >= 0; i--) { |
| 155 | onLayer[i] = max(onLayer[i], onLayer[i + 1]); |
| 156 | } |
| 157 | int betweenLayers = max(0, (int)layers.size() - 1); |
| 158 | int bSzLog = (llg + 1) >> 1; |
| 159 | int bSz = 1 << bSzLog; |
| 160 | indexSz = (n + bSz - 1) >> bSzLog; |
| 161 | v.resize(n + indexSz); |
| 162 | pref.assign(layers.size(), vector<SqrtTreeItem>(n + indexSz)); |
| 163 | suf.assign(layers.size(), vector<SqrtTreeItem>(n + indexSz)); |
| 164 | between.assign(betweenLayers, vector<SqrtTreeItem>((1 << llg) + bSz)); |
| 165 | build(0, 0, n, 0); |
| 166 | } |
| 167 | }; |
| 168 | int main() { |
| 169 | int i, j, k, n, m, q, l, r; |