主席树 + 二分答案

对于这种区间内的值域问题一般用主席树进行求解。

因为数据范围只有1e6，所以不用离散化，直接建树即可。

题目要求找到区间内离p第k近的数，可以想到，这个问题具有单调性（某个区间长度有大于k个值，那么比这个区间长度更长的比如也有大于k个值）

于是我们可以二分答案这个距离，枚举离p距离为mid的范围(max(1, p - mid), min(p + mid, 1e6)

这样我们每次主席树上询问这个值域范围内的个数是否大于等于k判断枚举的mid是否可行，最后mid停下来的最小值就是答案。

#include 
    
     #define INF 0x3f3f3f3f#define full(a, b) memset(a, b, sizeof a)#define __fastIn ios::sync_with_stdio(false), cin.tie(0)#define pb push_backusing namespace std;typedef long long LL;inline int lowbit(int x){ return x & (-x); }inline int read(){    int ret = 0, w = 0; char ch = 0;    while(!isdigit(ch)){        w |= ch == '-', ch = getchar();    }    while(isdigit(ch)){        ret = (ret << 3) + (ret << 1) + (ch ^ 48);        ch = getchar();    }    return w ? -ret : ret;}inline int lcm(int a, int b){ return a / __gcd(a, b) * b; }template 
     
      inline A fpow(A x, B p, C lyd){    A ans = 1;    for(; p; p >>= 1, x = 1LL * x * x % lyd)if(p & 1)ans = 1LL * x * ans % lyd;    return ans;}const int N = 200005;const int M = 1000005;int _, n, m, tot, a[N], lc[M*20], rc[M*20], tree[M*20], root[N];int buildTree(int l, int r){    int cur = ++ tot;    if(l == r) return cur;    int mid = (l + r) >> 1;    buildTree(l, mid);    buildTree(mid + 1, r);    return cur;}int insert(int rt, int l, int r, int val){    int cur = ++ tot;    tree[cur] = tree[rt] + 1, lc[cur] = lc[rt], rc[cur] = rc[rt];    if(l == r) return cur;    int mid = (l + r) >> 1;    if(val <= mid) lc[cur] = insert(lc[rt], l, mid, val);    else rc[cur] = insert(rc[rt], mid + 1, r, val);    return cur;}int query(int a, int b, int l, int r, int ql, int qr){    if(l == ql && r == qr){        return tree[b] - tree[a];    }    int mid = (l + r) >> 1;    if(qr <= mid) return query(lc[a], lc[b], l, mid, ql, qr);    else if(ql > mid) return query(rc[a], rc[b], mid + 1, r, ql, qr);    return query(lc[a], lc[b], l, mid, ql, mid) + query(rc[a], rc[b], mid + 1, r, mid + 1, qr);}bool calc(int l, int r, int p, int k, int mid){    int ret = query(root[l - 1], root[r], 1, M, max(1, p - mid), min(p + mid, M));    return ret >= k;}int main(){    //freopen("data.txt", "r", stdin);    for(_ = read(); _; _ --){        tot = 0;        n = read(), m = read();        for(int i = 1; i <= n; i ++) a[i] = read();        root[0] = buildTree(1, M);        for(int i = 1; i <= n; i ++){            root[i] = insert(root[i - 1], 1, M, a[i]);        }        int ans = 0;        while(m --){            int L = read(), R = read(), p = read(), k = read();            L ^= ans, R ^= ans, p ^= ans, k ^= ans;            int l = 0, r = 1e6;            while(l < r){                int mid = (l + r) >> 1;                if(calc(L, R, p, k, mid)) r = mid;                else l = mid + 1;            }            printf("%d\n", l);            ans = l;        }    }    return 0;}