HDU-6621 （杭电多校第4场 K-th Closest D

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=6621
比赛的时候觉得是主席树然后疯狂T，最后发现是比别人多了次二分然后在本机上跑了50s

这个题做法还蛮多的，主席树权值线段树都行。不过官方题解说是线段树+二分，然后发现节点存vector就行（怎么在比赛的时候没想到

Using segment tree, we can find the number of values smaller than p in [L, R] within .
So by using binary search method, we can find the answer in time.
Total time complexity is .

然后这个题就做完了，异常简单。。。也完全不卡常（不知道官方题解写那么长干啥

#include <algorithm>
#include <cstdio>
#include <iostream>
#include <vector>
using namespace std;

const int maxn = 100005;
int n, m;
int a[maxn];
vector<int> v[maxn << 2];
vector<int>::iterator it;

void build(int id, int l, int r)
{
    v[id].clear();
    for (int i = l; i <= r; i++) //把 l 到 r 的元素都存在vector中
        v[id].push_back(a[i]);
    sort(v[id].begin(), v[id].end());
    if (l == r)
        return;
    int mid = (l + r) >> 1;
    build(id << 1, l, mid);
    build(id << 1 | 1, mid + 1, r);
}

int query(int id, int L, int R, int l, int r, int h)
{
    if (l <= L && R <= r)
    {
        //当查待询区间[L, R] 完全包含 [l, r] 则返回该区间的结果
        it = upper_bound(v[id].begin(), v[id].end(), h);
        //找到第一个比val大的位置
        return it - v[id].begin();
        //相减得到小于等于val的个数
    }
    int mid = (L + R) >> 1;
    int ans = 0;
    if (l <= mid)
        ans += query(id << 1, L, mid, l, r, h);
    // 有一部分区间在 [L,mid] 之间
    if (mid < r)
        ans += query(id << 1 | 1, mid + 1, R, l, r, h);
    //有一部分在 [mid+1, R] 之间
    return ans;
}

int main()
{
    int T;
    scanf("%d", &T);
    while (T--)
    {
        int mxv;
        scanf("%d%d", &n, &m);
        for (int i = 1; i <= n; i++)
            scanf("%d", &a[i]);
        build(1, 1, n);
        int ans = 0;
        mxv = *max_element(a + 1, a + 1 + n);
        while (m--)
        {
            int l, r, p, k;
            scanf("%d%d%d%d", &l, &r, &p, &k);
            l ^= ans, r ^= ans, p ^= ans, k ^= ans;
            int begin = 0, end = mxv;
            while (end >= begin)
            {
                int hf = (begin + end) / 2;
                int t = query(1, 1, n, l, r, p + hf) - query(1, 1, n, l, r, p - hf - 1);
                if (t < k)
                {
                    begin = hf + 1;
                }
                else
                {
                    end = hf - 1;
                }
            }
            printf("%d\n", ans = begin);
        }
    }
    return 0;
}

线段树的部分参考：https://blog.csdn.net/piaocoder/article/details/48227623