LPOJ 欢迎来到实力至上主义的教室 —— 线段树合并

本文主要是介绍LPOJ 欢迎来到实力至上主义的教室 —— 线段树合并，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接：点我啊╭(╯^╰)╮

题目大意：

    中文题

解题思路：

    线段树维护答案，每个叶子节点维护一颗权值线段树
    合并右 $k$ 个点就是先 $merge$ ，然后二分删掉 $k$ 左边的点

核心：线段树合并

正常合并：

#include<bits/stdc++.h>
#define rint register int
#define deb(x) cerr<<#x<<" = "<<(x)<<'\n';
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 5;	
vector <int> v;
int n, q, tot, cnt, a[maxn], root[maxn];
int t0[maxn<<2], ls[maxn*40], rs[maxn*40];
struct node1{int op, x, y, l, r, v, k;
} Q[maxn];struct node{int mx, mi, num;node(){mi = 2e9, mx = num = 0;}node operator + (const node &A)const{node ret;ret.num = num + A.num;ret.mi = min(mi, A.mi);ret.mx = max(mx, A.mx);return ret;}
} t[maxn*40];void update(int &rt, int pos, int l, int r){if(l>pos || r<pos) return;if(!rt) rt = ++tot;if(l == r){t[rt].mi = t[rt].mx = l;t[rt].num++;return;}int m = l + r >> 1;update(ls[rt], pos, l, m);update(rs[rt], pos, m+1, r);t[rt] = t[ls[rt]] + t[rs[rt]];
}void update0(int pos, int c, int l, int r, int rt, int op){if(l>pos || r<pos) return;if(l == r){if(op) update(root[l], c, 1, cnt);if(t[root[l]].mi == 2e9) t0[rt] = 0;else t0[rt] = v[t[root[l]].mx] - v[t[root[l]].mi];return;}int m = l + r >> 1;update0(pos,c,l,m,rt<<1,op);update0(pos,c,m+1,r,rt<<1|1,op);t0[rt] = max(t0[rt<<1], t0[rt<<1|1]);
}int query(int L, int R, int l, int r, int rt){if(l>R || r<L) return 0;if(L<=l && r<=R) return max(0, t0[rt]);int m = l + r >> 1, ret = 0;ret = max(ret, query(L, R, l, m, rt<<1));ret = max(ret, query(L, R, m+1, r, rt<<1|1));return ret;
}int merge(int x, int y){if(!x || !y) return x + y;int now = ++tot;ls[now] = merge(ls[x], ls[y]);rs[now] = merge(rs[x], rs[y]);t[now] = t[ls[now]] + t[rs[now]];return now;
}void gao(int rt, int k, int l, int r){if(l == r){t[rt].num = min(t[rt].num, k);return ;}int cntr = t[rs[rt]].num, m = l + r >> 1;if(cntr < k) gao(ls[rt], k-cntr, l, m);else {ls[rt] = 0;gao(rs[rt], k, m+1, r);}t[rt] = t[ls[rt]] + t[rs[rt]];
}int getid(int x){return lower_bound(v.begin(), v.end(), x) - v.begin();
}int main() {scanf("%d", &n);v.push_back(-1);for(int i=1; i<=n; i++){scanf("%d", a+i);v.push_back(a[i]);}scanf("%d", &q);for(int i=1; i<=q; i++){scanf("%d", &Q[i].op);if(Q[i].op == 1) {scanf("%d%d", &Q[i].x, &Q[i].v);v.push_back(Q[i].v);} else if(Q[i].op == 2) scanf("%d%d", &Q[i].l, &Q[i].r);else scanf("%d%d%d", &Q[i].x, &Q[i].y, &Q[i].k);}sort(v.begin(), v.end());v.erase(unique(v.begin(), v.end()), v.end());cnt = v.size();for(int i=1; i<=n; i++) update0(i, getid(a[i]), 1, n, 1, 1);for(int i=1; i<=q; i++){if(Q[i].op == 1) update0(Q[i].x, getid(Q[i].v), 1, n, 1, 1);else if(Q[i].op == 2) printf("%d\n", query(Q[i].l, Q[i].r, 1, n, 1));else {int x = Q[i].x, y = Q[i].y, k = Q[i].k;root[x] = merge(root[x], root[y]);gao(root[x], k, 1, cnt);root[y] = 0;update0(x,0,1,n,1,0);update0(y,0,1,n,1,0);}}
}

---

暴力合并：

#include<bits/stdc++.h>
#define rint register int
#define deb(x) cerr<<#x<<" = "<<(x)<<'\n';
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 5;	
vector <int> v;
int n, q, tot, cnt, a[maxn], root[maxn];
int t0[maxn<<2], ls[maxn*150], rs[maxn*150];
struct node1{int op, x, y, l, r, v, k;
} Q[maxn];struct node{int mx, mi, num;node(){mi = 2e9, mx = num = 0;}node operator + (const node &A)const{node ret;ret.num = num + A.num;ret.mi = min(mi, A.mi);ret.mx = max(mx, A.mx);return ret;}
} t[maxn*150];void update(int &rt, int pos, int l, int r){if(l>pos || r<pos) return;if(!rt) rt = ++tot;if(l == r){t[rt].mi = t[rt].mx = l;t[rt].num++;return;}int m = l + r >> 1;update(ls[rt], pos, l, m);update(rs[rt], pos, m+1, r);t[rt] = t[ls[rt]] + t[rs[rt]];
}void update0(int pos, int c, int l, int r, int rt, int op){if(l>pos || r<pos) return;if(l == r){if(op) update(root[l], c, 1, cnt);if(t[root[l]].mi == 2e9) t0[rt] = 0;else t0[rt] = v[t[root[l]].mx] - v[t[root[l]].mi];return;}int m = l + r >> 1;update0(pos,c,l,m,rt<<1,op);update0(pos,c,m+1,r,rt<<1|1,op);t0[rt] = max(t0[rt<<1], t0[rt<<1|1]);
}int query(int L, int R, int l, int r, int rt){if(l>R || r<L) return 0;if(L<=l && r<=R) return max(0, t0[rt]);int m = l + r >> 1, ret = 0;ret = max(ret, query(L, R, l, m, rt<<1));ret = max(ret, query(L, R, m+1, r, rt<<1|1));return ret;
}int merge(int x, int y, int k, int l, int r){if((!x && !y) || !k) return 0;if(l == r){int now = ++tot, cnt = t[x].num + t[y].num;t[now].num = min(k, cnt);if(t[now].num) t[now].mi = t[now].mx = l;return now;}int m = l + r >> 1;if(!x){int now = ++tot, cnt = t[rs[y]].num;if(cnt >= k){ls[now] = 0;rs[now] = merge(0, rs[y], k, m+1, r);} else {ls[now] = merge(0, ls[y], k-cnt, l, m);rs[now] = rs[y];}t[now] = t[ls[now]] + t[rs[now]];return now;}	if(!y){int now = ++tot, cnt = t[rs[x]].num;if(cnt >= k){ls[now] = 0;rs[now] = merge(rs[x], 0, k, m+1, r);} else {ls[now] = merge(ls[x], 0, k-cnt, l, m);rs[now] = rs[x];}t[now] = t[ls[now]] + t[rs[now]];return now;}int now = ++tot, cnt = t[rs[x]].num + t[rs[y]].num;if(cnt >= k){ls[now] = 0;rs[now] = merge(rs[x], rs[y], k, m+1, r);} else {ls[now] = merge(ls[x], ls[y], k-cnt, l, m);rs[now] = merge(rs[x], rs[y], cnt, m+1, r);}t[now] = t[ls[now]] + t[rs[now]];return now;
}int getid(int x){return lower_bound(v.begin(), v.end(), x) - v.begin();
}int main() {scanf("%d", &n);v.push_back(-1);for(int i=1; i<=n; i++){scanf("%d", a+i);v.push_back(a[i]);}scanf("%d", &q);for(int i=1; i<=q; i++){scanf("%d", &Q[i].op);if(Q[i].op == 1) {scanf("%d%d", &Q[i].x, &Q[i].v);v.push_back(Q[i].v);} else if(Q[i].op == 2) scanf("%d%d", &Q[i].l, &Q[i].r);else scanf("%d%d%d", &Q[i].x, &Q[i].y, &Q[i].k);}sort(v.begin(), v.end());v.erase(unique(v.begin(), v.end()), v.end());cnt = v.size();for(int i=1; i<=n; i++) update0(i, getid(a[i]), 1, n, 1, 1);for(int i=1; i<=q; i++){if(Q[i].op == 1) update0(Q[i].x, getid(Q[i].v), 1, n, 1, 1);else if(Q[i].op == 2) printf("%d\n", query(Q[i].l, Q[i].r, 1, n, 1));else {int x = Q[i].x, y = Q[i].y, k = Q[i].k;root[x] = merge(root[x], root[y], k, 1, cnt);root[y] = 0;update0(x,0,1,n,1,0);update0(y,0,1,n,1,0);}}
}

这篇关于LPOJ 欢迎来到实力至上主义的教室 —— 线段树合并的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---