静的区間転倒数2

領域O(n)、構築O(n*sqrt(n/log(n)))、クエリO(sqrt(n*log(n)))、を示す数列を大バケットと小バケットの2種類のバケットで分割するn : 数列長 B : 大バケットのサイズ b : 小バケットのサイズ n=Bb大バケットがb個ある、小バケットがB個ある、b≦sqrt(n)≦B、と…

動的WMのB木による高速化の可能性について

WM(ウェーブレット行列)は上位ビットからの基数ソートのようなものであること、基数ソートを1ビット単位で行うより8ビット単位で行うほうが速そうであること、以上のことから動的WMも8ビット単位で行うと速くなるかもしれないので試すことにした次の処理がで…

静的区間転倒数

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(クエ…

動的平方分割(sumlt)

要素の追加削除ができる平方分割について考えるNを最大入力件数、bs(バケットサイズ)を√Nで固定、バケットへの要素の追加削除がO(√N)、バケットの追加削除がO(N)とする添字0,1,2のバケット3個が使われているとする→ (0,1,2)要素の追加でバケット1が満杯にな…

動的ウェーブレット行列

ウェーブレット行列を動的ビットベクトルを使って動的にしてある。1件の大きさを最大入力値のビットサイズとしたときn件の入力に対してメモリ8n程で動く。 (1ノードに128ビット持たせてビット演算とかに負荷をかけるとメモリ5n程で動くみたいなトレードオフ…

動的ウェーブレット木

ウェーブレット木的データ構造を平衡二分探索木を使って動的にしてある。 まだ書いてる途中でたぶんバグも残ってるので注意。 #include <iostream> #include <stdlib.h> #include <time.h> using namespace std; #define uint unsigned int class WaveletTree2{ private: struct node{ ui</time.h></stdlib.h></iostream>…

テスト

テスト int i; // テスト int i;