題目鏈接：http://acm.hdu.edu.cn/showproblem.php?pid=6621
比賽的時候覺得是主席樹然后瘋狂T趟妥，最后發(fā)現(xiàn)是比別人多了次二分然后在本機上跑了50s
這個題做法還蠻多的，主席樹權(quán)值線段樹都行瞎饲。不過官方題解說是線段樹+二分，然后發(fā)現(xiàn)節(jié)點存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 intime.
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)
{
//當查待詢區(qū)間[L, R] 完全包含 [l, r] 則返回該區(qū)間的結(jié)果
it = upper_bound(v[id].begin(), v[id].end(), h);
//找到第一個比val大的位置
return it - v[id].begin();
//相減得到小于等于val的個數(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
