JGZAfR - Online C++0x Compiler & Debugging Tool

// LET ME COOK
#include<bits/stdc++.h>
#define int long long
#define endl '\n'
#define sz(x) (int)x.size()
using namespace std;

struct BIT {
    vector<int> bit1, bit2;
    int n;

    void init(int _n) {
        n = _n;
        bit1.assign(n+5, 0);
        bit2.assign(n+5, 0);
    }

    void updatePoint(vector<int>& b, int u, int v) {
        int idx = u;
        while (idx <= n) {
            b[idx] += v;
            idx += (idx & (-idx));
        }
    }

    void updateRange(int l, int r, int v) {
        updatePoint(bit1, l, (n - l + 1) * v);
        updatePoint(bit1, r + 1, -(n - r) * v);
        updatePoint(bit2, l, v);
        updatePoint(bit2, r + 1, -v);
    }

    int getsum(vector<int>& b, int u) {
        int idx = u, ans = 0;
        while (idx > 0) {
            ans += b[idx];
            idx -= (idx & (-idx));
        }
        return ans;
    }

    int prefixsum(int u) {
        return getsum(bit1, u) - getsum(bit2, u) * (n - u);
    }

    int rangesum(int l, int r) {
        return prefixsum(r) - prefixsum(l - 1);
    }
};

struct query {
    int l, r, id;
};

BIT bit;
const int N = 2e5+5;
const int T = 2e5;
vector<pair<int,int>> have;
vector<int> ans(N);
vector<query> q;
int a[N];
int n, que;

void bs(int l, int r, vector<query> Q, vector<pair<int,int>> can) {
    if (l==r || Q.empty()) {
        for(auto p : Q) {
            ans[p.id] = l;
        }
        return;
    }

    int mid = l+r>>1;

    vector<pair<int,int>> L, R;
    vector<query> QL, QR;


    for(auto [val, id] : can) {
        if (val <= mid) {
            bit.updateRange(id, id, 1);
            L.push_back({val, id});
        } else {
            R.push_back({val, id});
        }
    }


    for(int i = 0 ; i < sz(Q); i++) {
        int tmp = bit.rangesum(Q[i].l, Q[i].r);
        int len = Q[i].r - Q[i].l + 1;
        int check = (len+1)/2;


        if (tmp >= check) {
            ans[Q[i].id] = mid;
            QL.push_back(Q[i]);
        } else {
            QR.push_back(Q[i]);
        }
    }


    bit.init(n+5);
    bs(l, mid, QL, L);
    bs(mid+1, r, QR, R);
}

void Semicolon() {
    cin >> n >> que;

    for(int i = 1; i <= n; i++) {
        cin >> a[i];
        have.push_back({a[i], i});
    }

    for(int i = 1; i <= que; i++) {
        int l, r; cin >> l >> r;
        q.push_back({l, r, i});
    }

    bit.init(n+5);
    bs(1, T, q, have);

    for(int i = 1; i <= que; i++) {
        cout << ans[i] << endl;
    }
}

signed main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    //freopen("", "r", stdin);
    //freopen("", "w", stdout);
    //freopen("input.txt", "r", stdin);
    Semicolon();

    return 0;
}