log は定数 [yukicoder No.670]

https://yukicoder.me/problems/no/670

解法

https://yukicoder.me/submissions/246681

配列aをソートして二分探索で答えを求めるO(QlogN)解法はTLEする。
そこで、配列aをNV毎に分割してそれぞれで二分探索をすることにする。
cnt2[v] := a[i]/NV≦vを満たす要素数
dic[v] := a[i]/NV=vである要素の集合
これを事前に計算しておこう。提出解ではNV=301010としてある。
配列dicの全ての集合は昇順ソートしておく。
　
こうすることで、答えは「cnt2[x/NV-1]+（dic[x/NV]でx以下の個数）」とできる。
前半はO(1)で、後半も入力がランダムであり意地悪ができないため、ほぼO(1)である。

int N, Q;
const int NV = 301010;
int cnt2[101010];
vector<int> dic[101010];
void _main() {
    cin >> N >> Q >> seed;
    for (int i = 0; i < 10000; i++) next();

    vector<int> a(N);
    for (int i = 0; i < N; i++) a[i] = next();
    
    rep(i, 0, N) {
        cnt2[a[i] / NV]++;
        dic[a[i] / NV].push_back(a[i]);
    }
    rep(i, 1, 101010) cnt2[i] += cnt2[i - 1];
    rep(i, 0, 101010) sort(all(dic[i]));

    ll sm = 0;
    for (int i = 0; i < Q; i++) {
        int x = next();

        int cnt = 0;
        int y = x / NV;
        if(y) cnt += cnt2[y - 1];
        cnt += lower_bound(all(dic[y]), x) - dic[y].begin();
        sm ^= ll(cnt) * i;
    }
    cout << sm << endl;
}