网站调用字体,建站网站关键词大全,图片在线制作生成器免费,红光网站建设array
给一个全排列#xff0c;接下来有两种操作#xff1a;
一、把pospospos位置上的值10,000,00010,000,00010,000,000。
二、查询[1,r][1, r][1,r]区间#xff0c;没有出现的且≥k\geq k≥k的最小值是多少。
考虑用主席树 set 求解#xff0c;
先建立一颗主席树接下来有两种操作
一、把pospospos位置上的值10,000,00010,000,00010,000,000。
二、查询[1,r][1, r][1,r]区间没有出现的且≥k\geq k≥k的最小值是多少。
考虑用主席树 set 求解
先建立一颗主席树每个叶节点的权值为其所代表的区间一个点的值然后维护区间最小值即可。
然后权值插入每次把这个点的权值跟新为infinfinf这一步也可以理解为在这个区间出现的数就是infinfinf了所以我们只要查询最小值即可求得这个区间没有出现得数。
思考一下我们的答案只可能≤n1\leq n 1≤n1所以对于操作一我们把修改得权值加入setsetset对于操作二我们在对应主席树上查找区间最小值即可然后与在setsetset查找得最优答案取minminmin即可。
#include bits/stdc.husing namespace std;const int N 1e5 10, inf 0x3f3f3f3f;int a[N], n, m;int ls[N 5], rs[N 5], minn[N 5], root[N], cnt;void push_up(int rt) {minn[rt] min(minn[ls[rt]], minn[rs[rt]]);
}void build(int rt, int l, int r) {rt cnt;if (l r) {minn[rt] l;return ;}int mid (l r) 1;build(ls[rt], l, mid);build(rs[rt], mid 1, r);push_up(rt);
}void update(int rt, int pre, int l, int r, int x, int v) {rt cnt, ls[rt] ls[pre], rs[rt] rs[pre], minn[rt] minn[pre];if (l r) {minn[rt] v;return ;}int mid (l r) 1;if (x mid) {update(ls[rt], ls[pre], l, mid, x, v);}else {update(rs[rt], rs[pre], mid 1, r, x, v);}push_up(rt);
}int query(int rt, int l, int r, int L, int R) {if (l L r R) {return minn[rt];}int mid (l r) 1, ans 0x3f3f3f3f;if (L mid) {ans min(ans, query(ls[rt], l, mid, L, R));}if (R mid) {ans min(ans, query(rs[rt], mid 1, r, L, R));}return ans;
}int main() {// freopen(in.txt, r, stdin);// freopen(out.txt, w, stdout);// ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);int T;scanf(%d, T);while (T--) {scanf(%d %d, n, m);const int N n 1;cnt 0;build(root[0], 1, N);for (int i 1; i n; i) {scanf(%d, a[i]);update(root[i], root[i - 1], 1, N, a[i], inf);}int last 0, op, t1, t2;setint st;for (int i 1; i m; i) {scanf(%d %d, op, t1);if (op 1) {t1 ^ last;st.insert(a[t1]);}else {scanf(%d, t2);t1 ^ last, t2 ^ last;last inf;last query(root[t1], 1, N, t2, N);auto it st.lower_bound(t2);if (it ! st.end()) {last min(last, *it);}printf(%d\n, last);}}}return 0;
}
