https://suisen-kyopro.hatenablog.com/entry/2022/10/15/010252 が面白かったです。読んで考えたことについて書きます。 0バケットサイズ、n=数列長)領域 O(max(pow(n,2(1-x)),pow(n,1+x))) 構築 O(max(pow(n,2-x),pow(n,1+x))) クエリ O(bs) タイプ1(クエリ区間が2つ以上のブロック(バケット)に跨るケース)は次のように計算する I(XYZ) = I(X) + I(Y) + I(Z) + I(X,Y) + I(Y,Z) + I(X,Z)I(X),I(Y),I(Z)は前計算で求…