当前位置 博文首页 > ttoobne：HDU6703 CCPC-网络赛 1002 array （主席树 + set）/（
题目链接
题解：
解法一：
由于序列所有元素都是唯一的，在 1 ~ n 的范围内。
如果只有操作 2 ，就可以用主席树维护权值，查询在树中
a
r
+
1
a_{r+1}
ar+1? 到
a
n
a_n
an? 区间大于等于 k 的最小的数，但是还有操作 1。
操作 1 可以视为为操作 2 提供答案（因为加了一个很大的值，查询保证
k
≤
n
k\leq n
k≤n，那加了之后的值就查不到了），这样的话进行操作 1 ，就将
a
p
o
s
a_{pos}
apos? 插入 set 中，查询时主席树查一遍，set 中用 lower_bound 查询一遍，取最小值即可。时间复杂度O(mlogn)。
解法二（题解做法）：
建一棵权值线段树维护权值的下标，每次操作一就是将该权值的下标设置为无穷大，操作二就是查询线段树中下标大于 r 的权值在 k ~ n 的最小值。
由于直接查可能会超时，所以线段树改为维护下标最大值方便剪枝。
解法一代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define PI acos(-1.0)
#define INF 0x3f3f3f3f3f3f3f3f
#define P pair<ll, int>
#define debug(x) cout << (#x) << ": " << (x) << " "
#define fastio ios::sync_with_stdio(false), cin.tie(0)
const ull mod = 1e9 + 7;
const int M = 15 + 10;
const int N = 100000 + 10;
int t, n, m, a[N];
struct node {
int ls, rs;
int num;
} tree[N<<5];
int rt[N], cnt;
set<int> s;
void build(int &now, int l, int r)
{
now = ++cnt;
tree[now].num = 0;
if(l == r) return ;
int mid = (l + r) >> 1;
build(tree[now].ls, l, mid);
build(tree[now].rs, mid + 1, r);
}
void add(int &now, int pre, int val, int l, int r)
{
now = ++cnt;
tree[now] = tree[pre];
tree[now].num ++;
if(l == r) return ;
int mid = (l + r) >> 1;
if(val <= mid) add(tree[now].ls, tree[pre].ls, val, l, mid);
else add(tree[now].rs, tree[pre].rs, val, mid + 1, r);
}
int query(int p, int q, int L, int R, int l, int r)
{
if(tree[q].num - tree[p].num == 0) return -1;
if(l == r) {
if(tree[q].num - tree[p].num) return l;
return -1;
}
int mid = (l + r) >> 1, ans = -1;
if(L <= mid) ans = query(tree[p].ls, tree[q].ls, L, R, l, mid);
if(mid < R && ans == -1) ans = query(tree[p].rs, tree[q].rs, L, R, mid + 1, r);
return ans;
}
int main()
{
scanf("%d", &t);
while(t --) {
s.clear();
cnt = 0;
scanf("%d %d", &n, &m);
s.insert(n + 1);
build(rt[0], 1, n);
for(int i = 1; i <= n; i ++) {
scanf("%d", &a[i]);
add(rt[i], rt[i - 1], a[i], 1, n);
}
int lastans = 0;
for(int i = 1, op; i <= m; i ++) {
scanf("%d", &op);
if(op == 1) {
int t1; scanf("%d", &t1);
int pos = t1 ^ lastans;
s.insert(a[pos]);
} else {
int t2, t3; scanf("%d %d", &t2, &t3);
int r = t2 ^ lastans, k = t3 ^ lastans;
lastans = query(rt[n], rt[r], k, n, 1, n);
int temp = *(s.lower_bound(k));
if(lastans != -1) lastans = min(lastans, temp);
else lastans = temp;
printf("%d\n", lastans);
}
}
}
return 0;
}
/*
Rejoicing in hope, patient in tribulation.
*/
/*
,----------------, ,---------,
,-----------------------, ," ,"|
," ,"| ," ," |
+-----------------------+ | ," ," |
| .-----------------. | | +---------+ |
| | | | | | -==----`| |
| | | | | | | |
| | Accepted _ | | |/----|`---= | |
| | | | | ,/|==== OOO | ;
| | | | | // |(((( [33]| ,"
| `-----------------` |," .//| |(((( | ,"
+-----------------------+ // | | |,"
/_)______________(_/ //` | +---------+
___________________________/___ `,
/ oooooooooooooooo .o. oooo /, \,"-----------
/ ==ooooooooooooooo==.o. ooo= // ,`\--{)B ,"
/_==__==========__==_ooo__ooo=_/` /___________,"
*/
解法二代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define PI acos(-1.0)
#define INF 0x3f3f3f3f3f3f3f3f
#define P pair<ll, int>
#define debug(x) cout << (#x) << ": " << (x) << " "
#define fastio ios::sync_with_stdio(false), cin.tie(0)
const int mod =
