线段树优化建图
算法流程
复杂度分析
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 5e5, M = 5e6 + 9;
struct Edge{
int v, w, nex;
} e[M];
int head[M], ecnt;
void AddEdge(int u, int v, int w){
e[++ecnt] = Edge{v, w, head[u]};
head[u] = ecnt;
}
int t[M], n, q, s;
void build(int id, int L, int R){
if(L == R){
t[L] = id;
AddEdge(id, id + N, 0);
AddEdge(id + N, id, 0);
return;
}
int mid = (L + R) >> 1;
AddEdge(id, id << 1, 0);
AddEdge(id, id << 1 | 1, 0);
AddEdge((id << 1) + N, id + N, 0);
AddEdge((id << 1 | 1) + N, id + N, 0);
build(id << 1, L, mid);
build(id << 1 | 1, mid + 1, R);
}
void connect(int u, int id, int L, int R, int qL, int qR, int qx, int type){
if(L == qL && R == qR){
if(type == 2)
AddEdge(u, id, qx);
else
AddEdge(id + N, u, qx);
return;
}
int mid = (L + R) >> 1;
if(qR <= mid)
connect(u, id << 1, L, mid, qL, qR, qx, type);
else if(qL > mid)
connect(u, id << 1 | 1, mid + 1, R, qL, qR, qx, type);
else {
connect(u, id << 1, L, mid, qL, mid, qx, type);
connect(u, id << 1 | 1, mid + 1, R, mid + 1, qR, qx, type);
}
}
int dis[M];
queue <int> qu;
bool inq[M];
void spfa(){
memset(dis, 0x3f3f, sizeof(dis));
dis[t[s]] = 0;
qu.push(t[s]);
inq[t[s]] = true;
while(!qu.empty()){
int u = qu.front();
for(int i = head[u]; i; i = e[i].nex){
int v = e[i].v;
if(dis[v] > dis[u] + e[i].w){
dis[v] = dis[u] + e[i].w;
if(!inq[v]){
qu.push(v);
inq[v] = true;
}
}
}
qu.pop();
inq[u] = false;
}
}
signed main(){
scanf("%lld%lld%lld", &n, &q, &s);
build(1, 1, n);
for(int i = 1; i <= q; i++){
int opt, u, v, w, L, R;
scanf("%lld%lld", &opt, &u);
if(opt == 1){
scanf("%lld%lld", &v, &w);
AddEdge(t[u], t[v], w);
} else {
scanf("%lld%lld%lld", &L, &R, &w);
connect(t[u], 1, 1, n, L, R, w, opt);
}
}
spfa();
for(int i = 1; i <= n; ++i)
if(dis[t[i]] == 0x3f3f3f3f3f3f3f3f)
printf("-1 ");
else
printf("%lld ", dis[t[i]]);
return 0 ;
}
线段树合并
前置知识:动态开点线段树
回忆普通线段树,它的空间一般要开到数组长度的 \(4\) 倍 (因此经常MLE),考虑如何优化它。
前置知识:权值线段树
算法流程
复杂度分析
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 9, LOGN = 22;
struct Edge{
int v, nex;
} e[N << 1];
int head[N], ecnt;
void addEdge(int u, int v){
e[++ecnt] = Edge{v, head[u]};
head[u] = ecnt;
}
struct Node{
int ls, rs, sum, res;
} t[50 * N];
int ans[N], cnt;
void update(int x){
if(t[t[x].ls].sum < t[t[x].rs].sum) {
t[x].res = t[t[x].rs].res;
t[x].sum = t[t[x].rs].sum;
} else {
t[x].res = t[t[x].ls].res;
t[x].sum = t[t[x].ls].sum;
}
}
int modify(int a, int b, int l, int r) {
if(!a)
return b;
if(!b)
return a;
if(l == r) {
t[a].sum += t[b].sum;
return a;
}
int mid = (l + r) >> 1;
t[a].ls = modify(t[a].ls, t[b].ls, l, mid);
t[a].rs = modify(t[a].rs, t[b].rs, mid + 1, r);
update(a);
return a;
}
int Build(int id, int l, int r, int co, int z) {
if(!id)
id = ++cnt;
if(l == r) {
t[id].sum += z;
t[id].res = co;
return id;
}
int mid = (l + r) >> 1;
if(co <= mid)
t[id].ls = Build(t[id].ls, l, mid, co, z);
else
t[id].rs = Build(t[id].rs, mid + 1, r, co, z);
update(id);
return id;
}
int fa[N][LOGN], dep[N], rt[N];
void dfs1(int u){
for(int i = head[u]; i; i = e[i].nex){
int v = e[i].v;
if(v != fa[u][0]){
fa[v][0] = u;
dep[v] = dep[u] + 1;
dfs1(v);
}
}
}
int query(int x, int y){
if(dep[x] > dep[y])
swap(x, y);
int d = dep[y] - dep[x];
int t = 0;
while(d){
if(d & 1)
y = fa[y][t];
++t;
d >>= 1;
}
t = 0;
while(fa[x][t] != fa[y][t])
++t;
--t;
while(t >= 0){
if(fa[x][t] != fa[y][t]){
x = fa[x][t];
y = fa[y][t];
}
--t;
}
if(x != y){
x = fa[x][0];
y = fa[y][0];
}
return x;
}
void dfs2(int u) {
for(int i = head[u]; i; i = e[i].nex) {
int v = e[i].v;
if(v == fa[u][0])
continue;
dfs2(v);
rt[u] = modify(rt[u], rt[v], 1, 100000);
}
ans[u] = t[rt[u]].res;
if(t[rt[u]].sum == 0)
ans[u] = 0;
}
int n, m;
int main(){
scanf("%d%d", &n, &m);
for(int i = 1; i < n; i++){
int u, v;
scanf("%d%d", &u, &v);
addEdge(u, v);
addEdge(v, u);
}
dfs1(1);
for(int j = 1, j2 = 2; j2 <= n; ++j, j2 <<= 1)
for(int i = 1; i <= n; ++i)
fa[i][j] = fa[fa[i][j - 1]][j - 1];
for(int i = 1; i <= m; i++){
int x, y, z;
scanf("%d%d%d", &x, &y, &z);
int lca = query(x, y);
rt[x] = Build(rt[x], 1, 100000, z, 1);
rt[y] = Build(rt[y], 1, 100000, z, 1);
rt[lca] = Build(rt[lca], 1, 100000, z, -1);
if(fa[lca][0])
rt[fa[lca][0]] = Build(rt[fa[lca][0]], 1, 100000, z, -1);
}
dfs2(1);
for(int i = 1; i <= n; i++)
printf("%d\n", ans[i]);
return 0;
}
线段树分裂
算法流程
复杂度分析
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 2e5 + 9;
struct Tree{
int ls, rs, sum;
} t[N << 5];
int rub[N << 5], rt[N << 2], cnt, tot, n, m, idx = 1;
int New(){
return cnt ? rub[cnt--] : ++tot;
}
void del(int &p){
t[p].ls = t[p].rs = t[p].sum = 0;
rub[++cnt] = p;
p = 0;
}
int build(int id, int L, int R) {
if(!id)
id = New();
if(L == R){
scanf("%lld", &t[id].sum);
return id;
}
int mid = (L + R) >> 1;
t[id].ls = build(t[id].ls, L, mid);
t[id].rs = build(t[id].rs, mid + 1, R);
t[id].sum = t[t[id].ls].sum + t[t[id].rs].sum;
return id;
}
int update(int id, int L, int R, int co, int z) {
if(!id)
id = New();
if(L == R) {
t[id].sum += z;
return id;
}
int mid = (L + R) >> 1;
if(co <= mid)
t[id].ls = update(t[id].ls, L, mid, co, z);
else
t[id].rs = update(t[id].rs, mid + 1, R, co, z);
t[id].sum = t[t[id].ls].sum + t[t[id].rs].sum;
return id;
}
int merge(int a, int b, int L, int R) {
if(!a)
return b;
if(!b)
return a;
if(L == R) {
t[a].sum += t[b].sum;
del(b);
return a;
}
int mid = (L + R) >> 1;
t[a].ls = merge(t[a].ls, t[b].ls, L, mid);
t[a].rs = merge(t[a].rs, t[b].rs, mid + 1, R);
t[a].sum = t[t[a].ls].sum + t[t[a].rs].sum;
del(b);
return a;
}
void split(int &p, int &q, int L, int R, int qL, int qR){
if(!p)
return;
if(L == qL && R == qR){
q = p;
p = 0;
return;
}
if(!q)
q = New();
int mid = (L + R) >> 1;
if(qR <= mid)
split(t[p].ls, t[q].ls, L, mid, qL, qR);
else if(qL > mid)
split(t[p].rs, t[q].rs, mid + 1, R, qL, qR);
else{
split(t[p].ls, t[q].ls, L, mid, qL, mid);
split(t[p].rs, t[q].rs, mid + 1, R, mid + 1, qR);
}
t[p].sum = t[t[p].ls].sum + t[t[p].rs].sum;
t[q].sum = t[t[q].ls].sum + t[t[q].rs].sum;
}
int query(int id, int L, int R, int qL, int qR){
if(!id)
return 0;
if(L == qL && R == qR)
return t[id].sum;
int ans = 0;
int mid = (L + R) >> 1;
if(qR <= mid)
ans += query(t[id].ls, L, mid, qL, qR);
else if(qL > mid)
ans += query(t[id].rs, mid + 1, R, qL, qR);
else
ans += query(t[id].ls, L, mid, qL, mid) + query(t[id].rs, mid + 1, R, mid + 1, qR);
return ans;
}
int kth(int id, int L, int R, int q){
if(L == R)
return L;
int mid = (L + R) >> 1;
int l = t[t[id].ls].sum;
if(q <= l)
return kth(t[id].ls, L, mid, q);
else
return kth(t[id].rs, mid + 1, R, q - l);
}
signed main(){
scanf("%lld%lld", &n, &m);
rt[1] = build(rt[1], 1, n);
while(m--){
int opt, p, x, y, tt, q, k;
scanf("%lld", &opt);
if(opt == 0){
scanf("%lld%lld%lld", &p, &x, &y);
split(rt[p], rt[++idx], 1, n, x, y);
} else if(opt == 1){
scanf("%lld%lld", &p, &tt);
rt[p] = merge(rt[p], rt[tt], 1, n);
} else if(opt == 2){
scanf("%lld%lld%lld", &p, &x, &q);
rt[p] = update(rt[p], 1, n, q, x);
} else if(opt == 3){
scanf("%lld%lld%lld", &p, &x, &y);
printf("%lld\n", query(rt[p], 1, n, x, y));
} else {
scanf("%lld%lld", &p, &k);
if(t[rt[p]].sum < k)
printf("-1\n");
else
printf("%lld\n", kth(rt[p], 1, n, k));
}
}
return 0;
}
可持久化线段树
算法流程
复杂度分析
#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 9;
int a[N], b[N], root[N], cnt, n, m;
struct{
int L, R, sum;
} tree[N << 5];
int build(int pl, int pr){
int rt = ++cnt;
tree[rt].sum = 0;
int mid = (pl + pr) >> 1;
if(pl < pr){
tree[rt].L = build(pl, mid);
tree[rt].R = build(mid + 1, pr);
}
return rt;
}
int modify(int pre, int pl, int pr, int x){
int rt = ++cnt;
tree[rt].L = tree[pre].L;
tree[rt].R = tree[pre].R;
tree[rt].sum = tree[pre].sum + 1;
int mid = (pl + pr) >> 1;
if(pl < pr){
if(x <= mid)
tree[rt].L = modify(tree[pre].L, pl, mid, x);
else
tree[rt].R = modify(tree[pre].R, mid + 1, pr, x);
}
return rt;
}
int query(int u, int v, int pl, int pr, int k){
if(pl == pr)
return pl;
int x = tree[tree[v].L].sum - tree[tree[u].L].sum;
int mid = (pl + pr) >> 1;
if(x >= k)
return query(tree[u].L, tree[v].L, pl, mid, k);
else
return query(tree[u].R, tree[v].R, mid + 1, pr, k - x);
}
int main(){
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; i++){
scanf("%d", &a[i]);
b[i] = a[i];
}
sort(b + 1, b + n + 1);
int size = unique(b + 1, b + n + 1) - (b + 1);
for(int i = 1; i <= n; i++){
int x = lower_bound(b + 1, b + size + 1, a[i]) - b;
root[i] = modify(root[i - 1], 1, size, x);
}
while(m--){
int x, y, k;
scanf("%d%d%d", &x, &y, &k);
printf("%d\n", b[query(root[x - 1], root[y], 1, size, k)]);
}
return 0;
}
李超线段树
算法流程
复杂度分析
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 9, MOD1 = 39989, MOD2 = 1e9;
const double eps = 1e-9;
struct Line{
double k, b;
} l[N];
struct Comp{
double res;
int id;
};
int s[N << 1], lcnt;
int cmp(double x, double y){
if(x - y > eps)
return 1;
else if(y - x > eps)
return -1;
else
return 0;
}
double calc(int id, int x){
return l[id].b + x * l[id].k;
}
void modify(int id, int L, int R, int u){
int &v = s[id], mid = (L + R) >> 1;
int flag = cmp(calc(u, mid), calc(v, mid));
if(flag == 1 || (!flag && u < v))
swap(u, v);
int flagl = cmp(calc(u, L), calc(v, L)), flagr = cmp(calc(u, R), calc(v, R));
if(flagl == 1 || (!flagl && u < v))
modify(id << 1, L, mid, u);
if(flagr == 1 || (!flagr && u < v))
modify(id << 1 | 1, mid + 1, R, u);
}
void update(int id, int L, int R, int qL, int qR, int u){
if(L == qL && R == qR){
modify(id, L, R, u);
return;
}
int mid = (L + R) >> 1;
if(qR <= mid)
update(id << 1, L, mid, qL, qR, u);
else if(qL > mid)
update(id << 1 | 1, mid + 1, R, qL, qR, u);
else {
update(id << 1, L, mid, qL, mid, u);
update(id << 1 | 1, mid + 1, R, mid + 1, qR, u);
}
}
Comp pmax(Comp x, Comp y) {
if(cmp(x.res, y.res) == -1)
return y;
else if(cmp(x.res, y.res) == 1)
return x;
else
return x.id < y.id ? x : y;
}
Comp query(int id, int L, int R, int k){
if(R < k || k < L)
return Comp{0, 0};
int mid = (L + R) >> 1;
double res = calc(s[id], k);
if(L == R)
return Comp{res, s[id]};
return pmax(Comp{res, s[id]}, pmax(query(id << 1, L, mid, k), query(id << 1 | 1, mid + 1, R, k)));
}
int n, lastans;
int main(){
scanf("%d", &n);
while(n--){
int op, k, x0, y0, x1, y1;
scanf("%d", &op);
if(op == 0){
scanf("%d", &k);
k = (k + lastans - 1 + MOD1) % MOD1 + 1;
printf("%d\n", lastans = query(1, 1, MOD1, k).id);
} else {
scanf("%d%d%d%d", &x0, &y0, &x1, &y1);
x0 = (x0 + lastans - 1 + MOD1) % MOD1 + 1;
x1 = (x1 + lastans - 1 + MOD1) % MOD1 + 1;
y0 = (y0 + lastans - 1 + MOD2) % MOD2 + 1;
y1 = (y1 + lastans - 1 + MOD2) % MOD2 + 1;
if(x0 > x1){
swap(x0, x1);
swap(y0, y1);
}
lcnt++;
if(x0 == x1){
l[lcnt].k = 0;
l[lcnt].b = max(y0, y1);
} else {
l[lcnt].k = (y1 - y0) * 1.0 / (x1 - x0);
l[lcnt].b = y0 - l[lcnt].k * x0;
}
update(1, 1, MOD1, x0, x1, lcnt);
}
}
return 0;
}