【每日一题】4月9日 Running Median

离散化+权值线段树

离散化：排序去重

权值线段树：区间维护的是有多少个数大于等于且小于等于。

#include <bits/stdc++.h>
using namespace std;
#define LL long long
const int INF = 0x3f3f3f3f;     ///1 061 109 567
const int negative_infinite = 0xcfcfcfcf;   ///-808 464 433
const double pi = acos(-1);
const int mod = 1e9 + 7;
const double eps = 1e-8;
const int MAXN = 1e4 + 117;
const int MAXM = 2e5 + 117;

int t;
int id, n, m;
int a[MAXN], b[MAXN], tree[MAXN * 4];
void Hash() {
    for(int i = 1; i <= n; i++) b[i] = a[i];
    sort(b + 1, b + 1 + n);
    m = unique(b + 1, b + 1 + n) - b - 1;
    memset(tree, 0, sizeof(tree));
}
int gethash(int x) {
    return lower_bound(b + 1, b + 1 + m, x) - b;
}
void update(int i, int l, int r, int x) {
    tree[i]++;
    if(l == r) return;
    int mid = (l + r) / 2;
    if(x <= mid) update(i * 2, l, mid, x);
    else update(i * 2 + 1, mid + 1, r, x);
}
int query(int i, int l, int r, int k) {
    if(l == r) return l;
    int mid = (l + r) / 2;
    if(k <= tree[i * 2]) return query(i * 2, l, mid, k);
    else return query(i * 2 + 1, mid + 1, r, k - tree[i * 2]);
}
int main() {
    scanf("%d", &t);
    while(t--) {
        scanf("%d%d", &id, &n);
        printf("%d %d\n", id, n / 2 + 1);
        for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
        Hash();
        for(int i = 1; i <= n; i++) {
            update(1, 1, m, gethash(a[i]));
            if(i % 2 != 0)
                printf("%d ", b[query(1, 1, m, i / 2 + 1)]);
            if(i % 20 == 0) putchar(10);
        }
        putchar(10);
    }
    return 0;
}

对顶堆

学习到了新的知识。

• 把序列按值的大小分成两个堆，两个堆的大小相差不超过1。
• 值小的一部分用大顶堆维护，这样堆顶的值是小的一部分中的最大值。
• 值大的一部分用小顶堆维护，这样堆顶的值是大的一部分中的最小值。
• 整个序列的中位数一定是较大的一个堆的堆顶。

记录一个小bug：

• vector<int> v;
for(int i=0;i<v.size();i++);
  会报warning: comparison between signed and unsigned integer expressions
• priority_queue<int> a,b;
if(a.size() - 1 > b.size());
  会进行无符号数运算。。。

#include <bits/stdc++.h>
using namespace std;
#define LL long long
const int INF = 0x3f3f3f3f;     ///1 061 109 567
const int negative_infinite = 0xcfcfcfcf;   ///-808 464 433
const double pi = acos(-1);
const int mod = 1e9 + 7;
const double eps = 1e-8;
const int MAXN = 1e4 + 117;
const int MAXM = 2e5 + 117;

int t;
int id, n, x;
int main() {
    scanf("%d", &t);
    while(t--) {
        scanf("%d%d", &id, &n);
        printf("%d %d\n", id, n / 2 + 1);
        priority_queue<int> big;//存小的一半
        priority_queue<int, vector<int>, greater<int>> small;//存大的一半
        for(int i = 1; i <= n; i++) {
            scanf("%d", &x);
            if(big.empty() || x <= big.top()) big.push(x);
            else small.push(x);
            if(big.size() > small.size() + 1) {
                small.push(big.top());
                big.pop();
            }
            if(small.size() > big.size() + 1) {
                big.push(small.top());
                small.pop();
            }
            if(i & 1) printf("%d ", big.size() > small.size() ? big.top() : small.top());
            if(i % 20 == 0) putchar(10);
        }
        putchar(10);
    }
    return 0;
}