[2019杭电多校第四场][hdu6621]K-th Closest Distance（主席树）

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=6621

题意为求区间[l,r]内第k小|a[i]-p|的值。

可以二分答案，如果二分的值为x，则判断区间[l,r]内是否有k个数在[p-x,p+x]范围内。所以就用主席树搞一下。

 #include<iostream>

 #include<algorithm>

 #include<cstring>

 #include<string>

 #include<cmath>

 #include<vector>

 #define lson l, mid, i<<1

 #define rson  mid + 1, r, i<<1|1

 using namespace std;

 typedef long long ll;

 const int maxn = 1e6 + ;

 int root[maxn], rs[maxn * ], ls[maxn * ], val[maxn * ];

 int cnt;

 void update(int k, int l, int r, int &i) {

     val[++cnt] = val[i] + , ls[cnt] = ls[i], rs[cnt] = rs[i];

     i = cnt;

     if (l == r)

         return;

     int mid = l + r >> ;

     if (k <= mid)

         update(k, l, mid, ls[i]);

     else

         update(k, mid + , r, rs[i]);

 }

 int query(int u, int v, int L, int R, int l, int r) {

     if (L <= l && r <= R)

         return val[u] - val[v];

     int mid = l + r >> ;

     int ans = ;

     if (L <= mid)

         ans += query(ls[u], ls[v], L, R, l, mid);

     if (R > mid)

         ans += query(rs[u], rs[v], L, R, mid + , r);

     return ans;

 }

 int check(int L, int R, int p, int x) {

     int l = max(p - x, ), r = min(p + x, (int)1e6);

     return query(root[R], root[L - ], l, r, , 1e6);

 }

 int main() {

     int t;

     scanf("%d", &t);

     while (t--) {

         int n, m, x, cnt = ;

         scanf("%d%d", &n, &m);

         for (int i = ; i <= n; i++) {

             scanf("%d", &x);

             root[i] = root[i - ];

             update(x, , 1e6, root[i]);

         }

         int ans = , L, R, p, k;

         for (int i = ; i <= m; i++) {

             scanf("%d%d%d%d", &L, &R, &p, &k);

             L ^= ans, R ^= ans, p ^= ans, k ^= ans;

             int l = , r = 1e6;

             while (l <= r) {

                 int mid = l + r >> ;

                 int w = check(L, R, p, mid);

                 if (w >= k) {

                     r = mid - ;

                     ans = mid;

                 }

                 else

                     l = mid + ;

             }

             printf("%d\n", ans);

         }

     }

 }