HDU6703 权值线段树

题意： 给定一个长度为 $n$n的排列 $q$q，即 $n$n个元素值都属于 $1\sim n$1∼n，且 $n$n个元素互不相同。
修改操作：将 $q\left[pos\right]$q[pos]加上 $1e7$1e7。查询操作：找到与 $q[1\sim r]$q[1∼r]都不相同的且不小于 $k$k的最小值。

题解： 通过分析可得，查询的答案最大为 $n+1$n+1，即我们每次只需要从 $[k,n+1]$[k,n+1]中查找答案即可。对于每次修改操作，加上 $1e7$1e7相当于在 $1\sim r$1∼r中删除这个数，所以将其索引置为INF即可。
线段树叶节点表示权值，维护每个区间中最大的索引，二分查询 $[k,n+1]$[k,n+1]这个区间，由于是权值线段树故先查询左子树，再查询右子树。注意题目中 $pos,r,k$pos,r,k都要异或上前一次查询的答案。

代码：

#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;

const int N = 1e5 + 10;
int q[N], pos[N], T, n, m;
int ans;
int op, r, k, pos1;

struct Node{
	int l, r;
	int p;
}tr[N << 2];

void pushup(int u) {
	tr[u].p = max(tr[u << 1].p, tr[u << 1 | 1].p);
}

void build(int u, int l, int r) {
	tr[u] = {l, r, 0};
	if(l == r) {
		tr[u].p = pos[l];
		return ;
	}
	
	int mid = l + r >> 1;
	build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
	pushup(u);
}

void modify(int u, int x) {
	if(tr[u].l == tr[u].r) {
		tr[u].p = n + 1;
		return ;
	}
	
	int mid = tr[u].l + tr[u].r >> 1;
	if(x <= mid) modify(u << 1, x);
	else modify(u << 1 | 1, x);
	pushup(u);
}

void query(int u, int l, int r, int Mpos) {
	if(tr[u].l == tr[u].r) {
		ans = tr[u].l;
		return ;
	}
	
	int mid = tr[u].l + tr[u].r >> 1;
	if(l <= mid && tr[u << 1].p > Mpos) query(u << 1, l, r, Mpos);
	if(ans == -1 && tr[u << 1 | 1].p > Mpos) query(u << 1 | 1, l, r, Mpos); 
}

int main()
{
	scanf("%d", &T);
	while(T--) {
		scanf("%d%d", &n, &m);
		for(int i = 1; i <= n; i++)
			scanf("%d", &q[i]), pos[q[i]] = i;
		pos[n + 1] = n + 1;
		build(1, 1, n + 1);
		
		ans = 0;
		while(m--) {
			scanf("%d", &op);
			if(op == 1) {
				scanf("%d", &pos1);
				pos1 ^= ans;
				modify(1, q[pos1]);
			}
			
			else {
				scanf("%d%d", &r, &k);
				r ^= ans, k ^= ans;
				ans = -1;
				query(1, k, n + 1, r);
				printf("%d\n", ans);
			}
		}
	}
	return 0;
}