[規格/C+]9426-測定中心値

質問リンク:https://www.acmicpc.net/problem/9426
質問する
気象学で主に用いられる代表値は中央値である.(ヒントに中心値の定義が示されています)
尚根には毎秒1回の温度を測定する機械があり、彼はこの機械に入るソフトウェアを作成しなければならない.機械には小さなデジタルディスプレイがあります.毎秒、K秒で測定した温度中心値が表示されます.
尚根はソフトウェアをアップロードする前にパソコンでテストしたいと思っています.
合計N秒の測定温度が与えられている場合は、表示される中心値の和を求めるプログラムを作成します.すなわち、N個の数が与えられた場合、長さKの連続部分数列N−K+1個の中央値の和を求めるプログラムを作成してください.
入力
第1行はNとKを与える.(1 ≤ N ≤ 250,000, 1 ≤ K ≤ 5,000, K ≤ N)
2行目からN行目に測定温度を順次与えた.温度が0以上、65535以下の整数.
しゅつりょく
出力長Kの全連続部分数列の中心値の和.
に答える

#include <iostream>
#include <algorithm>

class smt {
public:
	smt() { }

	int update(int node, int start, int end, int index, int num) {
		if (index < start || index > end) {
			return mTree[node];
		}
		else if (start == end) {
			mTree[node] += num;
			return mTree[node];
		}

		int mid = (start + end) / 2;

		mTree[node] = update(node * 2, start, mid, index, num) + update(node * 2 + 1, mid + 1, end, index, num);

		return mTree[node];
	}

	int query(int node, int start, int end, int num) {
		if (start == end) {
			return start;
		}

		int mid = (start + end) / 2;

		if (mTree[node * 2] >= num) {
			return query(node * 2, start, mid, num);
		}
		else {
			return query(node * 2 + 1, mid + 1, end, num - mTree[node * 2]);
		}
	}

private:
	int mTree[65536 * 4];
};

int arr[250001] = { 0, };
smt seg;

int main() {
	std::ios::sync_with_stdio(false);
	std::cout.tie(NULL);
	std::cin.tie(NULL);

	int N;
	int K;
	std::cin >> N >> K;

	for (int i = 0; i < N; i++) {
		std::cin >> arr[i];
	}

	for (int i = 0; i < K; i++) {
		seg.update(1, 0, 65536, arr[i], 1);
	}

	long long ans = seg.query(1, 0, 65536, (K + 1) / 2);

	for (int i = K; i < N; i++) {
		seg.update(1, 0, 65536, arr[i], 1);
		seg.update(1, 0, 65536, arr[i - K], -1);

		int mid = seg.query(1, 0, 65536, (K + 1) / 2);

		ans += mid;
	}

	std::cout << ans << "\n";

	return 0;
}

セグメントツリー
ノードを探索し続けることが重要です.
updateとqueryを容易に使用するために、クラスとして作成して使用します.
入力を受け付けるとupdateに進み、中央値が得られます.
ノート
条件を設定するのは難しくなく、ansがintを離れるとは思わなかった.
おかげで正解に近づいたものの、とんでもないことをたくさんしてしまったので、ずっと間違えていました.
最適なタイプ条件を考慮して、変数のタイプを指定します.