HDUOJ 6703 array (线段树）

solution：一看到这种题目就知道应该用线段树来做

#include <bits/stdc++.h>
using namespace std;

int n, m, arr[100001], tree[400001];

void build(int root, int l, int r)
{
	if (l == r){
		tree[root] = n + 1;
		return;
	}
	int mid = (l + r) >> 1;
	build(root << 1, l, mid);
	build(root << 1 | 1, mid + 1, r);
	tree[root] = max(tree[root << 1], tree[root << 1 | 1]);
}

//更新操作
void updata(int root, int l, int r, int val, int pos)
{
	if (l == r){
		tree[root] = pos;
		return;
	}
	int mid = (l + r) >> 1;
	if (val <= mid)updata(root << 1, l, mid, val, pos);
	else updata(root << 1 | 1, mid + 1, r, val, pos);
	tree[root] = max(tree[root << 1], tree[root << 1 | 1]);
}

int query(int root, int l, int r, int k, int lim)
{
	if (l == r){
		if (tree[root] > lim)return l;
		else return n + 1;
	}
	int mid = (l + r) >> 1, ans = n + 1;
	if (k <= mid && tree[root << 1] > lim){
		ans = query(root << 1, l, mid, k, lim);
	}
	if (ans == n + 1 && tree[root << 1 | 1] > lim){
		ans = query(root << 1 | 1, mid + 1, r, k, lim);
	}
	return ans;
}

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