题目链接：http://acm.hdu.edu.cn/contests/contest_showproblem.php?pid=1008&cid=851
题目大意：
给一个数组，每次给 l ,r, p, k，问区间 [l, r] 的数与 p 的绝对值的第 k 小，这个绝对值是多少。

思路：

把问题转化成求一个ans使得：区间[l, r]上值域 [p - ans, p + ans]的数的个数>=k。的ans的最小值。二分ans就可以了， 注意边界的处理。

#include <bits/stdc++.h>
#define LL long long
using namespace std;
#define mid (l+r)/2
const int maxn=2e5+10;

int root[maxn]={0}, L[maxn*60]={0}, R[maxn*60]={0}, sum[maxn*60]={0};
int n, m, cut=0, Len=0;

int BT(int l, int r)
{
    int rt=++cut;
    sum[rt]=0;
    if(l<r)
    {
        L[rt]=BT(l, mid);
        R[rt]=BT(mid+1, r);
    }

    return rt;
}

int gx(int i, int l, int r, int x)
{
    int rt=++cut;
    L[rt]=L[i], R[rt]=R[i], sum[rt]=sum[i]+1;

    if(l<r)
    {
        if(x<=mid)
        {
            L[rt]=gx(L[i], l, mid, x);
        }
        else
        {
            R[rt]=gx(R[i], mid+1, r, x);
        }
    }

    return rt;
}

int cx(int i, int l, int r, int x, int y)
{
    if(x>r||x>y)
    {
        return 0;
    }
    if(l==x&&r==y)
    {
        return sum[i];
    }

    if(y<=mid)
    {
        return cx(L[i], l, mid, x, y);
    }
    else if(x>mid)
    {
        return cx(R[i], mid+1, r, x, y);
    }
    else
    {
        return cx(L[i], l, mid, x, mid)+cx(R[i], mid+1, r, mid+1, y);
    }
}

int a[maxn], b[maxn];

int solve(int x)
{
    int pl, pr, p, k;
    scanf("%d%d%d%d", &pl, &pr, &p, &k);
    pl^=x, pr^=x, p^=x, k^=x;

    if(pl>pr)
    {
        swap(pl, pr);
    }

    int l=0, r=1e6+5, pmid=0;
    while(l<=r)
    {
        int ans=(l+r)/2;
        int t1=p-ans;
        int t2=p+ans;
        t1 = lower_bound(b+1, b+Len+1, t1) -b;
        t2 = upper_bound(b+1, b+Len+1, t2) -b;
        t2--;//右边界的处理
        
        if(cx(root[pr], 1, Len, t1, t2)-cx(root[pl-1], 1, Len, t1, t2)>=k)
        {
            pmid=ans;
            r=ans-1;
        }
        else
        {
            l=ans+1;
        }
    }
    printf("%d\n", pmid);

    return pmid;
}

int main()
{
    int t;
    scanf("%d", &t);
    while(t--)
    {
        cut=0;
        memset(sum, 0, sizeof(sum));
        scanf("%d%d", &n,&m);
        for(int i=1;i<=n;i++)
        {
            scanf("%d", &a[i]);
            b[i]=a[i];
        }

        sort(b+1, b+n+1);
        Len=unique(b+1, b+n+1)-(b+1);

        root[0]=BT(1, Len);
        for(int i=1;i<=n;i++)
        {
            a[i]=lower_bound(b+1, b+Len+1, a[i]) -b;
            root[i]=gx(root[i-1], 1, Len, a[i]);
        }
        int x=0;
        while(m--)
        {
            x=solve(x);
        }

    }
    return 0;
}