E&F 小红的中位数查询

有一个序列 ， 次查询，每次查询一个长度为奇数的子区间 的中位数。

，。

solution

这里提供一个比较劣的做法，但使用算法相对基础。

先把 离散化（但要记得存原值）假设权值的区间是 ，然后对于每个权值记 vector：，记录所有等于它的数的下标。

一种暴力的思想是，把 每个数都枚举一次，每次二分求出区间 内数字 的个数。

然后不断累加，直到数字个数大于 。

但是这么做的时间复杂度是 的（假设 同阶）。

这样太慢了，但我们可以考虑分块！以 为阈值，假设块长 。

大块的部分记录权值分别在 之中的数字个数随着下标增加的前缀和。

对于每次询问，我们一个个大块跑过去，判断加到哪个块的时候，累计的数字个数大于 ，记录这个块的左右端点 。

然后我们让 从 逐步往 减少，每次删掉区间 中等于 的数字个数，直到不满足数字个数大于 ，这个区间的中位数就是 了。

时间复杂度 ，可以勉强通过（假设 同阶）。

Code

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int INF = 1e9;

int n, m, q, sz, blk[100010], mm, s[410][100010];
int a[100010], b[100010], t[400010], l[100010], r[100010];
vector <int> v[100010];

signed main(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    cin >> n >> q;
    for(int i = 1; i <= n; i++) 
        cin >> a[i], b[i] = a[i];
    sort(b + 1, b + n + 1);
    m = unique(b + 1, b + n + 1) - b - 1;
    sz = (int)sqrt(m);
    for(int i = 1; i <= n; i++){
        a[i] = lower_bound(b + 1, b + m + 1, a[i]) - b;
        blk[i] = (i - 1) / sz + 1;
        v[a[i]].push_back(i);
    }
    mm = blk[n];
    for(int i = 1; i <= n; i++)
        s[blk[a[i]]][i]++;
    for(int i = 1; i <= mm; i++)
        for(int j = 1; j <= n; j++)
            s[i][j] += s[i][j - 1];    
    for(int i = 1, now, L, R; i <= n; i++){
        cin >> l[i] >> r[i], now = 0;
        for(int j = 1; j <= mm; j++){
            now += s[j][r[i]] - s[j][l[i] - 1];
            if(now > (r[i] - l[i] + 1) >> 1){
                L = (j - 1) * sz + 1;
                R = j * sz;
                break;
            }
        }
        if(now <= (r[i] - l[i] + 1) >> 1) continue;
        for(int j = R, p1, p2; j >= L; j--){
            p2 = upper_bound(v[j].begin(), v[j].end(), r[i]) - v[j].begin();
            p1 = lower_bound(v[j].begin(), v[j].end(), l[i]) - v[j].begin();
            now -= p2 - p1;
            if(now <= (r[i] - l[i] + 1) >> 1){
                printf("%d\n", b[j]);
                break;
            }
        }
    }
    return 0;
}