洛谷P3722 [AH2017/HNOI2017]影魔(线段树 set spaly)
程序员文章站
2022-12-15 08:58:49
题意 "题目链接" Sol 这题好毒瘤啊。。 首先要观察到几个性质: 1. 将最小值旋转到根相当于把右子树变为祖先的左子树,然后将原来的根变为当前最小值 2. 上述操作对深度的影响相当于右子树不变,其他的位置 1 然后就可以做了,把询问离线之后离散化一下,建一棵权值线段树表示每个值对应的深度 同时用 ......
题意
sol
这题好毒瘤啊。。
首先要观察到几个性质:
将最小值旋转到根相当于把右子树变为祖先的左子树,然后将原来的根变为当前最小值
上述操作对深度的影响相当于右子树不变,其他的位置-1
然后就可以做了,把询问离线之后离散化一下,建一棵权值线段树表示每个值对应的深度
同时用set维护出已经加入的值
每次先找到后继,看一下有没有左孩子,如果有的话说明前驱一定没有右孩子。
注意随时更新信息
复杂度\(o(nlogn)\)
#include<bits/stdc++.h> #define pair pair<ll, ll> #define mp(x, y) make_pair(x, y) #define fi first #define se second #define ll long long #define fin(x) {freopen(#x".in","r",stdin);} #define fout(x) {freopen(#x".out","w",stdout);} using namespace std; const int maxn = 1e6 + 10, mod = 1e9 + 7, inf = 1e9 + 10; inline int read() { char c = getchar(); int x = 0, f = 1; while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();} while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar(); return x * f; } int n, m, opt[maxn], val[maxn], date[maxn], cnt; void des() { sort(date + 1, date + cnt + 1); cnt = unique(date + 1, date + cnt + 1) - date - 1; for(int i = 1; i <= m; i++) if(opt[i] == 1) val[i] = lower_bound(date + 1, date + cnt + 1, val[i]) - date; } set<int> s; #define ls k << 1 #define rs k << 1 | 1 int add[maxn], root, f[maxn], ll[maxn], rr[maxn]; void ps(int k, int v) { add[k] += (rr[k] - ll[k] + 1) * v; f[k] += v; } void pushdown(int k) { if(!f[k]) return ; ps(ls, f[k]); ps(rs, f[k]); f[k] = 0; } void update(int k) { add[k] = add[ls] + add[rs]; } void build(int k, int ll, int rr) { if(ll == rr) return ; int mid = ll + rr >> 1; build(ls, ll, mid); build(rs, mid + 1, rr); } void intadd(int k, int l, int r, int ql, int qr, int v) { if(ql <= l && r <= qr) {ps(k, v); return ;} pushdown(k); int mid = l + r >> 1; if(ql <= mid) intadd(ls, l, mid, ql, qr, v); if(qr > mid) intadd(rs, mid + 1, r, ql, qr, v); update(k); } void modify(int k, int l, int r, int p, int v) { if(l == r) {add[k] = v; return ;} int mid = l + r >> 1; pushdown(k); if(p <= mid) modify(ls, l, mid, p, v); else modify(rs, mid + 1, r, p, v); update(k); } int query(int k, int l, int r, int p) { if(l == r) return add[k]; int mid = l + r >> 1; pushdown(k); if(p <= mid) return query(ls, l, mid, p); else return query(rs, mid + 1, r, p); } #undef ls #undef rs #define ls(x) ch[x][0] #define rs(x) ch[x][1] int ch[maxn][2], fa[maxn]; void connect(int x, int _fa, int tag) { if(x == _fa || (_fa == m + 1)) return ; ch[_fa][tag] = x; fa[x] = _fa; } int insert(int v) { if(s.empty()) {root = v; modify(1, 1, m, v, 1); s.insert(v); fa[v] = m + 1; return 1;} auto nxt = s.upper_bound(v); if(nxt != s.end() && !ls(*nxt)) { int pos = *nxt; modify(1, 1, m, v, query(1, 1, m, pos) + 1); connect(v, pos, 0); } else { nxt--; int pos = *nxt; modify(1, 1, m, v, query(1, 1, m, pos) + 1); connect(v, pos, 1); } s.insert(v); return query(1, 1, m, v); } int rotatemin() { int mn = *s.begin(), v = query(1, 1, m, mn); intadd(1, 1, m, mn + 1, fa[mn] - 1, -1); intadd(1, 1, m, 1, m, 1); modify(1, 1, m, mn, 1); connect(rs(mn), fa[mn], 0); connect(root, mn, 1); root = mn; fa[root] = m + 1; return v; } int rotatemax() { auto it = s.end(); it--; int mx = *it, v = query(1, 1, m, mx); intadd(1, 1, m, (fa[mx] == m + 1) ? 1 : fa[mx] + 1, mx - 1, -1); intadd(1, 1, m, 1, m, 1); modify(1, 1, m, mx, 1); connect(ls(mx), fa[mx], 1); connect(root, mx, 0); root = mx; fa[root] = m + 1; return v; } int deletmin() { int v = rotatemin(); int mn = *s.begin(); fa[rs(mn)] = m + 1; root = rs(mn); intadd(1, 1, m, 1, m, -1); modify(1, 1, m, mn, 0); fa[mn] = rs(mn) = ls(mn) = 0; s.erase(mn); return v; } int deletmax() { int v = rotatemax(); auto it = s.end(); it--; int mx = *it; fa[ls(mx)] = m + 1; root = ls(mx); intadd(1, 1, m, 1, m, -1); modify(1, 1, m, mx, 0); fa[mx] = ls(mx) = rs(mx) = 0; s.erase(mx); return v; } signed main() { m = read(); for(int i = 1; i <= m; i++) { opt[i] = read(); if(opt[i] == 1) val[i] = read(), date[++cnt] = val[i]; } build(1, 1, m); des(); for(int i = 1; i <= m; i++) { if(opt[i] == 1) printf("%d\n", insert(val[i])); else if(opt[i] == 2) printf("%d\n", rotatemin()); else if(opt[i] == 3) printf("%d\n", rotatemax()); else if(opt[i] == 4) printf("%d\n", deletmin()); else printf("%d\n", deletmax()); } return 0; } /* 4 1 39877 1 76497 2 1 6377 */
上一篇: 第一课《.net之--泛型》
下一篇: 最受黑客喜欢的五种网络口令