# 洛谷P3722 [AH2017/HNOI2017]影魔(线段树 set spaly)

## Sol

1. 将最小值旋转到根相当于把右子树变为祖先的左子树，然后将原来的根变为当前最小值
2. 上述操作对深度的影响相当于右子树不变，其他的位置-1

#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;
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) {
}
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) {
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() {
for(int i = 1; i <= M; i++) {
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
*/

0 条评论

• ### 洛谷T21778 过年

题目描述 有 n(1 \leq n \leq 10^5)n(1≤n≤105) 个小朋友，过年了，要发放 m(1 \leq m \leq 10^5)m(1≤m≤1...

• ### 洛谷P2447 [SDOI2010]外星千足虫(异或方程组)

找最优解可以考虑高斯消元的过程，因为异或的特殊性质，每次向下找的时候找到第一个1然后交换就行，这样显然是最优的

• ### 洛谷P1941 飞扬的小鸟(背包 dp)

很显然的dp，设$$f[i][j]$$表示第$$i$$个位置，高度为$$j$$的最小步数

• ### codechef September Challenge 2018 Division 2 A-F

最大的是：$2, 3, 4, 5, n / 2, 1, 2 + n / 2, 3 + n / 2, 4 + n /2 ...$

• ### 洛谷P2447 [SDOI2010]外星千足虫(异或方程组)

找最优解可以考虑高斯消元的过程，因为异或的特殊性质，每次向下找的时候找到第一个1然后交换就行，这样显然是最优的

• ### 洛谷T21778 过年

题目描述 有 n(1 \leq n \leq 10^5)n(1≤n≤105) 个小朋友，过年了，要发放 m(1 \leq m \leq 10^5)m(1≤m≤1...

• ### CSU1216: 异或最大值(01Trie树)

多组数据。第一行为数字个数n，1 <= n <= 10 ^ 5。接下来n行每行一个32位有符号非负整数。

• ### BZOJ 1061: [Noi2008]志愿者招募【单纯形裸题】

1061: [Noi2008]志愿者招募 Time Limit: 20 Sec  Memory Limit: 162 MB Submit: 4813  Solv...

• ### 洛谷P1941 飞扬的小鸟(背包 dp)

很显然的dp，设$$f[i][j]$$表示第$$i$$个位置，高度为$$j$$的最小步数