えーーーこれが平方分割的解法って天才すぎでは

問題概要

$N$ 人が一直線上を、初期位置 $X_i$ 、速度 $V_i$ で等速直線運動を行う。以下の $Q$ 個のクエリに答えよ:

$T$ 秒後に座標 $L$ から座標 $R$ までの間にいる人数を数えよ

制約

$1 \le N, Q \le 10^{5}$
$0 \le X_i \le 10^{5}$
$-10^{5} \le V_i \le 10^{5}$
$0 \le L \le R \le 10^{5}$

考えたこと

$L, R$ が $10^{5}$ 以下と小さいことが大きな味噌。

$T$ が大きいときは、速度が速いやつは遠く彼方に行ってしまう

というのが重要な考察で、具体的には

$T$ が小さいときは、愚直シミュレーションで前処理して求められる
$T$ が大きいときは、速度が $V$ が小さい範囲だけ考えればいい

ちょうどいい分岐として、 $10^{5}$ の平方根くらいでよい。計算量はちゃんとやれば $O((N + Q)\sqrt{R})$ になるはず (以下の実装はバケット法を一部さぼってにぶたんしているのでやや悪い)

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

const int MAX = 110000;
const int small = 500;

// 入力
int N, Q;
vector<int> X, V;

// small T
vector<vector<int> > pos;  // pos[t][x] := t 秒後の x 以内にどれだけいるか

// small V
vector<vector<int> > xss; // xs[v] := 速度 v - geta をもつ初期座標 x の集合

int main() {
    scanf("%d", &N);
    X.resize(N); V.resize(N);
    for (int i = 0; i < N; ++i) scanf("%d %d", &X[i], &V[i]);
    
    // small T を求める
    pos.assign(small, vector<int>(MAX+10, 0));
    for (int t = 0; t < small; ++t) {
        for (int i = 0; i < N; ++i) {
            long long tmp = (long long)(X[i]) + (long long)(V[i]) * t;
            if (tmp < 0 || tmp > MAX) continue;
            pos[t][tmp + 1]++;
        }
        for (int i = 0; i <= MAX; ++i) pos[t][i+1] += pos[t][i];
    }
    
    // small V を求める
    xss.assign(small*2 + 1, vector<int>());
    for (int i = 0; i < N; ++i) {
        if (V[i] < -small || V[i] > small) continue;
        xss[V[i] + small].push_back(X[i]);
    }
    for (auto &xs : xss) sort(xs.begin(), xs.end());
    
    // クエリに答える
    scanf("%d", &Q);
    for (int _ = 0; _ < Q; ++_) {
        int T, L, R;
        scanf("%d %d %d", &T, &L, &R);
        
        int num = 0;
        if (T < small) {
            num = pos[T][R+1] - pos[T][L];
        }
        else {
            for (int v = -small; v <= small; ++v) {
                int left = L - v * T;
                int right = R - v * T;
                int tmp = upper_bound(xss[v+small].begin(), xss[v+small].end(), right)
                - lower_bound(xss[v+small].begin(), xss[v+small].end(), left);
                num += tmp;
            }
        }
        printf("%d\n", num);
    }
}