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

// 私はあなたがいなくて寂しいです
// 你可以拖延，但时间不会。
// 雪花飄飄北風嘯嘯
// 天地一片蒼茫
/**
 *   author:  semicolon
*/
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <sstream>
#include <utility>
#include <numeric>
#include <iomanip>
#include <deque>
#include <queue>
#include <stack>
#include <list>
#include <iterator>
#include <climits>
#include <bitset>
#include <cassert>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <time.h>
#include <functional>
#include <forward_list>
#include <tuple>
#include <chrono>
#include <random>
//#pragma GCC optimize("O2,O3,unroll-loops")
//#pragma GCC target("avx,avx2,fma")
// #pragma GCC optimize("O2")
// #pragma GCC optimize("Ofast,fast-math")
// #pragma GCC optimize("no-stack-protector")
// #pragma GCC optimize("inline")
// #pragma GCC optimize("tree-vectorize")
// #pragma GCC optimize("tree-loop-distribute-patterns")
// #pragma GCC optimize("tree-loop-distribute-decls")
// #pragma GCC optimize("tree-loop-improve")
// #pragma GCC optimize("tree-loop-vectorize")
// #pragma GCC optimize("tree-vectorize-loops")
// #pragma GCC optimize("tree-vectorize-loops-aggressive")
// #pragma GCC optimize("tree-vectorize-loops-optimized")
// #pragma GCC optimize("tree-vectorize-loops-optimized-aggressive")
// #pragma GCC optimize("unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt")

using namespace std;
void debug_out() {cout << endl;}
template<typename Head, typename ...Tail>
void debug_out(Head H, Tail ...T) {
    cout << H << ' ';
    debug_out(T...);
}
void Semicolon();

#define coutmatrix(a,n,m) for(int i = 0; i < n; i++) {for(int j = 0; j < m; j++) {cout << a[i][j] << " ";}cout << endl;}
#define coutarr(a,n) for(int ix = 0;ix < n;ix++) {cout << a[ix] << " ";} cout << endl;
#define coutvec(a) for(int ix = 0;ix < a.size();ix++) {cout << a[ix] << " ";} cout << endl
#define runtime cerr<< "Time elapsed: " << (1.0*clock()/CLOCKS_PER_SEC)<< "s" << endl;
#define debug(...) cout << "[" << #__VA_ARGS__ << "]: ", debug_out(__VA_ARGS__)
#define For(i,n) for(int i = 0; i < n; i++)
#define Fod(i,a,b) for(int i = a; i <= b; i++)
#define Rev(i,n) for(int i = n-1; i >= 0; i++) //reverse
#define IOS ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define tcase() int t; cin >> t; while (t--) {Semicolon();};
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
#define setpr(x) cout<<fixed<<setprecision(x)
#define freo(s) freopen(s".INP","r",stdin); freopen(s".OUT","w",stdout);
#define fx(a,n) a,a+n
#define str stringstream
#define endl '\n'
#define pb push_back
#define pf push_front
#define popb pop_back
#define popf pop_front
#define eb emplace_back
#define ef emplace_front
#define ins insert
#define le length
#define fi first
#define se second
#define mkp make_pair
#define ci1(a) cin >> a
#define ci2(a, b) cin >> a >> b
#define ci3(a, b, c) cin >> a >> b >> c
#define ci4(a, b, c, d) cin >> a >> b >> c >> d
#define MXINT = INT_MAX
#define MNINT = INT_MIN
#define MXLONG = LONG_MAX
#define MNLONG = LONG_MIN
#define vvi vector<vector<int>>
#define vvl vector<vector<long long>>
#define segleft id<<1
#define segright id<<1|1
#define MASK(i) (1LL << (i))
#define BIT(x, i) (((x)>>(i)) & 1)
using ll = signed long long int;
using ull = unsigned long long int;
using ld = long double;
using lld = long double;
using pii = pair<int, int>;
using pll = pair<long long, long long>;
using pil = pair<int, long long>;
using pli = pair<long long, int>;
using vi = vector<int>;
using vl = vector<long long>;
using qi = queue<int>;
using q_pii = queue<pair<int,int>>;
using q_pll = queue<pair<long long,long long>>;
using mii = map<int,int>;
using mll = map<long long,long long>;
using mp_ivi = map<int, vector<int>>;
using mp_lvl = map<long long, vector<long long>>;
using mulmpi = multimap<int, int>;
using mulmpl = multimap<long long, long long>;
using dqi = deque<int>;
using dql = deque<long long>;
using sti = stack<int>;
using stl = stack<long long>;
using stpii = stack<pair<int,int>>;
using stpll = stack<pair<long long,long long>>;
using vpii = vector<pair<int,int>>;
using vpll = vector<pair<long long,long long>>;
using vpil = vector<pair<int,long long>>;
using vpli = vector<pair<long long,int>>;
using si = set<int>;
using sl = set<long long>;
const ll MOD = 1e9+7;
const ll MAXLL = LLONG_MAX;
const ll NMAXLL = -MAXLL;
const ll INF = INT_MAX;
const ll INFL = LLONG_MAX;
const long double pi = acos(-1.0);
const char compass[4] = {'N','W','E','S'};
const char dir[4] = {'U','R','D','L'};
const int dx[4] = {-1, 0, 1, 0};
const int dy[4] = {0, 1, 0, -1};
/// 0 = up (U), 1 = right (R), 2 = down (D), 3 = left (L)
const int dXy[] = {0, 0, -1, 1, 1, -1, 1, -1};
const int dYx[] = {-1, 1, 0, 0, 1, 1, -1, -1};

template<class X, class Y>
    bool minimize(X &x, const Y &y) {
        if (x > y) {
            x = y;
            return true;
        }
        return false;
    }
template<class X, class Y>
    bool maximize(X &x, const Y &y) {
        if (x < y) {
            x = y;
            return true;
        }
        return false;
    }

template<typename T>
class range {
    private:
       T last;
       T itr;
    public:
       range(T end, T start = 0) : last(end), itr(start) {}
       const range& begin() const { return *this; }
       const range& end() const { return *this; }
       bool operator!=(const range&) const { return itr < last; }
       void operator++() { ++itr; }
       T operator*() const { return itr; }
};
#define int long long
//#define ll long long
void iofile(string s) {
    freopen((s + ".inp").c_str(), "r", stdin);
    freopen((s + ".out").c_str(), "w", stdout);
}
int readInt() {
   int x; cin >> x; return x;
}

//#define LENGTH 1000005
//#define NMOD 2
//#define BASE 311
//const int Hashmod[] = {(int)1e9 + 7, (int)1e9 + 2277, (int)1e9 + 5277, (int)1e9 + 8277, (int)1e9 + 9277};

//mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
//mt19937 rnf(2106);

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
    //freopen("input.txt", "r", stdin);
    //iofile("");
    //freo("")
    //tcase();
    Semicolon();
    return 0;
}

/*
                                                 .........
                                                 .........
                                 .....        .....=*%%##*-.....
                            ...-##%%%%#+........-%@*------+#%%#................
                            .:%%%#+++#%%%#=:...:%%*-------::=%@%+::............
                        ....+%%#-------+%@@#-..%%#----+++=----+%%*=+:...::........
                     ......-%%#----------+#%*--++----=+++=-------=#%%%%%*=----:......
                    ......:#%%----+++=-------------------------------=#%%%%%+.........
                     ..:++=*#=----=+=------------------------------------=*%%%%=--:...
              ......=%@%%%+-------------------------------------------------=#%@@*:...
              ...-#%%%#+-------------------------------------------------------+%%%*.....
              ..#@%%+------------------------------------------------------------+%@@-....
          ....+%@%+------------------------------------------------------------::--#%%+.....
          ..:#%%*-:-----------------------------------------------------------------+%%*:....
       ....=%%%=:--------------------------------------------------------------------=%@#:...
       ...=%%*------------------------------------------------------------------------=#%#:..
      ...=@%+---------------------------------------....:------------------------------=#%#:..
      ..=%%*---------------------------------------:.....:------------------------------+%%*:...
     ..-%%#=------------------------.....:----------....:--------------------------------*%@:...
   ....*%%+------------------------:.....:-----------------------------------------------+%@*...
   ...:%%*:-------------------------:...:-------------------------------------------------#%%...
   ...#%%=--------------------------------------------------------------------------------#%%:..
   ..:#%#---------------------------------------------------------------------------------*%%:...
   ..=%%*---------------------------------------------------------------------------------*%%-...
   ..=%@=----------------------------------------------------------------==+==------------*%@-..
   ..+%@=--------------------------------------------------*%@%%==*=--=+++++++++=---------*%%-...
.....-%%*-------------------------------------:-----------*%%%%%@@+-=++++++++++++=--------#%@:..
.....:#%*---------------------------=**=:---------=-------+%%%%%@*--=+++++++++++++=------=%%*....
......#%%=------------------------+%%%%%#=-----=%%@%-......:%%%%+---+++++#%%@#++++-------*%@-
......+%%*------------------------*@%%%%@*-:....:*%=..............--=+%%%%%%%@@%+------+%%*.
.....--%%%=------------=+++++==---=#@%%@%=.......=%@-::............---*%%-......+%@@#*%%+:..
.....:-+%%*----------=+++++++++++---+##=........-#@%%%%*............---*%%-......+%@@#*%%+:..
....:---+%%+--------=+++++++++++++=--:..........*#=.................-=%%%%=........+%%%%=....
........-+%#=------==+++++++++++++=-:...............................=%%#:...........:#%%*:...
.......:-%%*--------=+++++++++++++=-:..............................:%@#...............-%%#-.........
   .....:@%*--------=++++++++++++=--:..........................-*%%%%@:...............:=#%%+:.......
       .:%%#=---------=+++++++==----:.......................:*%%%#*%%@-..............:--=*%%#.......
       ..-%%#=-----------====--------:................--===*%@*+=+=#@@:............:------*%%#......
       ...-#%%+------------------------:-+++++-..:+#%%%%%%@%#+=====+%%*:........::---------+%%#:....
        . ....-#@%%%####*######=-----*%%+=======*%%*======*%%+=======#%%+--------------------+%%*:..
          ......+%%@%@@%%@@@@@%+-----#%%=========*%#+======#@*=======+%%%*--------------------+%%*:
      ........+%@%#=----------------=*@%+======+=+%%*+**##%@%%%%%%%#%@%%%%#=-------------------+%%*-
      ......+%@%*--------------------=@%#========+#%%@@@%#+-.:--=*#%*=:-+%@%=-:-----------------*%%*
      ....-#%@*----------+=-----------+%%*======#%@*:...................:-*%*-------------------=#%%
      ..-+%@#=----------#@#=-----------*@%#*#%@@%*.......................-------------------------#%
      .:*@%*-----------+%%+-------------=*%%%#=...........................------------------------=
    ...+@%+.----------=@%*-----------------:..............................:------------------------+
   ...:%%*....:------=%%#------------------................................-------------------------
   ...=%%=......:----+%@+-----------------:................................:------------------------
    ..*%%:.........:-#%%------------------:................................:------------------------
   ...*%%-..........:#%#-------------------.................................------------------------
   ...-%%#:.........-#%*-------------------:................................------------------------
   ....=@%#-........-#@#--------------------:..................:::.........:------------------------
                               ........  ..  ....-#%%**##%@%*-........ ..   ..
*/