[题解] [JSOI2011] 棒棒糖

题面

题解

这个数据范围明显就是莫队嘛, 为啥不让我的莫队过啊
考虑主席树, 每次往区间内数的个数大于要求的那一边走
若没有, 代表没有满足要求的数
如果能走到 (l = r) , 那么这个数 (l) 就是我们要求的数了

Code

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
const int N = 50005;
const int lim = 50000; 
using namespace std;

int n, m, rt[N], cnt;
struct node { int l, r, sz; } t[N * 32]; 

template < typename T >
inline T read()
{
    T x = 0, w = 1; char c = getchar();
    while(c < '0' || c > '9') { if(c == '-') w = -1; c = getchar(); }
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * w; 
}

void modify(int &p, int o, int l, int r, int k)
{
    p = ++cnt, t[p] = t[o], t[p].sz++;
    if(l == r) return;
    int mid = (l + r) >> 1;
    if(k <= mid) modify(t[p].l, t[o].l, l, mid, k);
    else modify(t[p].r, t[o].r, mid + 1, r, k); 
}

int solve(int p, int o, int l, int r, int k)
{
    if(l == r)
	return l;
    int mid = (l + r) >> 1;
    if(t[t[p].l].sz - t[t[o].l].sz > k)
	return solve(t[p].l, t[o].l, l, mid, k);
    if(t[t[p].r].sz - t[t[o].r].sz > k)
	return solve(t[p].r, t[o].r, mid + 1, r, k);
    return 0; 
}

int main()
{
    n = read <int> (), m = read <int> ();
    for(int x, i = 1; i <= n; i++)
    {
	x = read <int> ();
	modify(rt[i], rt[i - 1], 1, lim, x); 
    }
    int l, r; 
    while(m--)
    {
	l = read <int> (), r = read <int> ();
	printf("%d
", solve(rt[r], rt[l - 1], 1, lim, (r - l + 1) / 2)); 
    }
    return 0; 
}