2019ccpc网络赛hdu6703 array(线段树)

朴灿烈づ我的快乐病毒、 2023-08-17 17:21 131阅读 0赞

# array #

[题目传送门][Link 1]

## 解题思路 ##

操作1是把第pos个位置上的数加上\\(10^7\\)，操作2是找到区间\[1,r\]中没有且大于k的最小的数。注意到k的范围是小于等于n的，且n的范围是\\(10^5\\)，远小于\\(10^7\\)，所以对于操作1，可以视为把第pos个位置上的数删去。

因为所有节点上的数都是唯一的，所以建立一颗权值线段树，存入每个权值对应的位置，维护其最大值和最小值。为了保证一定有答案，建立的权值范围是\[1,n+1\]。对于操作1，直接把pos对应的权值的叶子节点修改为0，代表这个数不存在即可。

对于操作2，我们在线段树上查询。对于一颗子树，有答案的前提是其最大值大于r，或者最小值等于0，即存在r后面的数，或者有不存在的数。对于左子树，还应有mid>=k。因为答案要尽量小，所以先看左子树是否可以找到答案，如果左子树没有答案，再看右子树，如果右子树也没有，则返回0，表示没有找到答案。但因为建立的权值范围是\[1,n+1\]，所以最后一定会有答案，当进入叶子节点，则返回答案。

## 代码如下 ##

#include <bits/stdc++.h> #define INF 0x3f3f3f3f using namespace std; typedef long long ll; const int N = 100005; struct T{ int l, r; int minn, maxx; }tree[N<<2]; void build(int k, int l, int r) { tree[k].l = l; tree[k].r = r; tree[k].maxx = tree[k].minn = 0; if(l == r) return; int mid = (l + r) / 2; build(2*k, l, mid); build(2*k+1, mid + 1, r); } void update(int k, int x, int v) { if(tree[k].l == tree[k].r){ tree[k].maxx = tree[k].minn = v; return; } int mid = (tree[k].l + tree[k].r) / 2; if(x <= mid) update(2*k, x, v); else update(2*k+1, x, v); tree[k].minn = min(tree[2*k].minn, tree[2*k+1].minn); tree[k].maxx = max(tree[2*k].maxx, tree[2*k+1].maxx); } int query(int k, int r, int x) { if(tree[k].l == tree[k].r) return tree[k].l; int mid = (tree[k].l + tree[k].r) / 2; if(x <= mid && (tree[2*k].minn == 0 || tree[2*k].maxx > r)){ int ans = query(2*k, r, x); if(ans) return ans; } if(tree[2*k+1].minn == 0 || tree[2*k+1].maxx > r) return query(2*k+1, r, x); else return 0; } int a[N]; int main() { int t; scanf("%d", &t); while(t --){ int n, m; scanf("%d%d", &n, &m); build(1, 1, n + 1); for(int i = 1; i <= n; i ++){ int x; scanf("%d", &x); a[i] = x; update(1, x, i); } int last = 0; for(int i = 1; i <= m; i ++){ int opt; scanf("%d", &opt); if(opt == 1){ int t1; scanf("%d", &t1); t1 ^= last; update(1, a[t1], 0); } else { int t1, t2; scanf("%d%d", &t1, &t2); t1 ^= last; t2 ^= last; last = query(1, t1, t2); printf("%d\n", last); } } } return 0; }

转载于:https://www.cnblogs.com/whisperlzw/p/11403816.html

[Link 1]: http://acm.hdu.edu.cn/showproblem.php?pid=6703