ちゅうしんち

白駿1572号:中央値

アイデア

キャンディボックスとの問題は多くありません.区間で順序を求める問題は,出現する可能性のあるすべての数値寸法範囲に従ってツリーを構築し,数値が現れるたびに個数を増やし,その区間で戻り個数の和を返すクエリを作成することができる.
最近K個の数字の中で1つの中央値を求めるので、キューの中で数字K,push,popを維持します.

コード#コード#

#include <bits/stdc++.h>

using namespace std;

const int MAX = 65536;
int N, K;

vector<int> tree(4*MAX, 0);

void update(int start, int end, int idx, int diff, int node) {
    if (idx < start || end < idx) return;
    tree[node] += diff;
    if (start == end) return;
    update(start, (start+end)/2, idx, diff, node*2);
    update((start+end)/2+1, end, idx, diff, node*2+1);
}

int getmid(int start, int end, int midx, int node) {
    if (start == end) {
        return start;
    }
    if (tree[node*2] < midx) {
        return getmid((start+end)/2+1, end, midx-tree[node*2], node*2+1);
    }
    else {
        return getmid(start, (start+end)/2, midx, node*2);
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> N >> K;
    int midx = K/2+1;
    if (K%2 == 0) midx--;
    int x;
    long long ans = 0;
    queue<int> q;
    for (int i = 0; i < K; i++) {
        cin >> x;
        q.push(x);
        update(0, MAX-1, x, 1, 1);
    }
    ans += getmid(0, MAX-1, midx, 1);
    for (int i = K; i < N; i++) {
        update(0, MAX-1, q.front(), -1, 1);
        q.pop();
        cin >> x;
        q.push(x);
        update(0, MAX-1, x, 1, 1);
        ans += getmid(0, MAX-1, midx, 1);
    }
    cout << ans;
    return 0;
}

おしゃべり

ほとんど解けたのにどうしてこんなに時間がかかったの?常に入力値と同じ範囲のツリーを作成することを考慮します.