題目鏈接：http://acm.hdu.edu.cn/showproblem.php?pid=6621
比賽的時(shí)候覺得是主席樹然后瘋狂T，最后發(fā)現(xiàn)是比別人多了次二分然后在本機(jī)上跑了50s

這個(gè)題做法還蠻多的，主席樹權(quán)值線段樹都行。不過官方題解說是線段樹+二分，然后發(fā)現(xiàn)節(jié)點(diǎn)存vector就行（怎么在比賽的時(shí)候沒想到

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 .

然后這個(gè)題就做完了，異常簡單。。。也完全不卡常（不知道官方題解寫那么長干啥

#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)
    {
        //當(dāng)查待詢區(qū)間[L, R] 完全包含 [l, r] 則返回該區(qū)間的結(jié)果
        it = upper_bound(v[id].begin(), v[id].end(), h);
        //找到第一個(gè)比val大的位置
        return it - v[id].begin();
        //相減得到小于等于val的個(gè)數(shù)
    }
    int mid = (L + R) >> 1;
    int ans = 0;
    if (l <= mid)
        ans += query(id << 1, L, mid, l, r, h);
    // 有一部分區(qū)間在 [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