http://poj.org/problem?id=3685

A_ij = i * i + 100,000 * i + j * j - 100,000 * j + i * j

で定義されるN次正方行列のM番目の値を調べる。

ある値x未満の数が行列中に何個あるかは
A_ijの値はjを固定したときiについて単調増加なので各列について二分探索をすればN * lg(N)で求められる。

x未満の数がM個未満となるような最大のxをとってくればそれが中央値。

{{{#!highlight c++

#include <iostream>

using namespace std;

typedef long long ll;

ll N, M;

ll count_lt(ll x) {
    ll cnt = 0;
    for (ll j = 1; j <= N; j++) {
        // [lb, ub)
        ll lb = 0, ub = N+1;
        while (lb + 1 < ub) {
            ll i = (lb + ub) / 2; // mid = i
            if (i * i + 100000 * i + j * j - 100000 * j + i * j < x) {
                lb = i;
            } else {
                ub = i;
            }
        }
        cnt += lb;
    }
    return cnt;
}

int main() {
    int T; // the number of test cases
    cin >> T;
    while (T--) {
        cin >> N >> M;
        ll lb = -1LL << 60, ub = 1LL << 60;
        while (lb + 1 < ub) {
            ll mid = (lb + ub) / 2;
            if (count_lt(mid) < M) {
                lb = mid;
            } else {
                ub = mid;
            }
        }
        cout << lb << endl;
    }
    return 0;
}



}}}