| 253 | } |
| 254 | |
| 255 | public static void prepare() { |
| 256 | dfs3(); |
| 257 | dfs4(); |
| 258 | blen = (int) Math.sqrt(n * 20); |
| 259 | bnum = (n + blen - 1) / blen; |
| 260 | for (int i = 1; i <= n; i++) { |
| 261 | bi[i] = (i - 1) / blen + 1; |
| 262 | } |
| 263 | for (int i = 1; i <= bnum; i++) { |
| 264 | bl[i] = (i - 1) * blen + 1; |
| 265 | br[i] = Math.min(i * blen, n); |
| 266 | bitSet[i] = new BitSet(); |
| 267 | for (int j = bl[i]; j <= br[i]; j++) { |
| 268 | bitSet[i].setOne(val[j]); |
| 269 | } |
| 270 | } |
| 271 | } |
| 272 | |
| 273 | public static void main(String[] args) throws IOException { |
| 274 | FastReader in = new FastReader(System.in); |