首页 > 其他分享 >线段树进阶应用学习笔记（一）（2024.7.19）（2024.8.22）

线段树进阶应用学习笔记（一）（2024.7.19）（2024.8.22）

时间：2024-09-20 16:47:32浏览次数：10  
标签：return 进阶 22 2024.7 int sum rs mid id

线段树优化建图

算法流程

复杂度分析

例题一

#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;
}

扫描线算法

标签：return,进阶,22,2024.7,int,sum,rs,mid,id
From： https://www.cnblogs.com/JPGOJCZX/p/18422794

相关文章

  • 平衡树学习笔记（一）（2024.7.20）
    二叉搜索树众所周知，一个区间可以有许多信息(最大值、\(k\)大值、区间和、区间平方和、区间立方和、区间异或和、区间\(\gcd\)、不同数字个数、颜色段数……)，也有许多修改方式(插入、删除、区间加、区间乘、区间改、区间翻转……)，我们发现其中一些用线段树不是很好维护，这时我们......
  • 快速幂模板/洛谷P1226【模板】快速幂
    ​本题是CSP-J组的第四题。题意：给出一个有向图，当前在1号点，初始在时间0，必须在k的倍数的时间出发，且到终点的时间也必须是k的倍数。每条边有一个边权，只有在当前时间≥时才可以通过，且不能在原地不动，即每一个时间点必须走一条边。问从11号点出发到nn号时最早的时刻。（没......
  • [ABC221H] Count Multiset
    题意思路参考了题解做法。设\(f_{i,j}\)表示填入\(i\)个数字，和为\(j\)的方案数。每次可以填入\(0\)，或者将整个数列\(+1\)。\(g_{i,j}\)表示填入\(i\)个数字，且这\(i\)个数字中没有\(0\)，何为\(j\)的方案数。易得\(g_{i,j}=f_{i,j-i}\)，表示在\(i\)......
  • 大模型入门到进阶：什么是Graph RAG？
    自从ChatGPT的出现引爆了人工智能的炒作之后，检索增强生成(RAG)就主导了关于如何让GenAI应用程序变得有用的讨论。这个想法很简单。一旦我们将LLM连接到我们的私人数据，它就会变得特别有用。每个人都可以访问的基础模型与我们特定领域的数据相结合，作为秘密武器，产生......
  • P3224 [HNOI2012] 永无乡
    题意思路用并查集维护连通性，每个集合维护一个平衡树，每次合并两个集合的时候，将一个平衡树的节点一个一个加入到另一个中。这么做不会超时，每次将小的平衡树拆掉放到大的中，可以证明不会超过\(O(\logn)\)次。总时间复杂度\(O(n\log^2n)\)。代码#include<bits/stdc++.h......
  • 兼收并蓄 TypeScript - 进阶: ArrayBuffer
    源码https://github.com/webabcd/TypeScriptDemo作者webabcd兼收并蓄TypeScript-进阶:ArrayBuffer示例如下:advanced\arrayBuffer.ts{/***1、ArrayBuffer-内存之中的一段二进制数据，需要通过视图操作数据*2、TypedArray-视图，用于操作ArrayBuf......
  • 兼收并蓄 TypeScript - 进阶: promise
    源码https://github.com/webabcd/TypeScriptDemo作者webabcd兼收并蓄TypeScript-进阶:promise示例如下:advanced\promise.ts{/***Promise-用于异步编程（非多线程）*有3种状态：pending（进行中），fulfilled（已成功），rejected（已失败）*状态只能从......
  • 兼收并蓄 TypeScript - 进阶: async/await
    源码https://github.com/webabcd/TypeScriptDemo作者webabcd兼收并蓄TypeScript-进阶:async/await示例如下:advanced\async_await.ts{/***async/await-用于异步编程（非多线程）*asyncfunction返回的是Promise对象*await用于等Pro......
  • 兼收并蓄 TypeScript - 进阶: iterator, generator
    源码https://github.com/webabcd/TypeScriptDemo作者webabcd兼收并蓄TypeScript-进阶:iterator,generator示例如下:advanced\iterator_generator.ts{/***iterator-迭代器（可迭代对象有Array,TypedArray,Map,Set,String）*next()-迭代到......
  • 兼收并蓄 TypeScript - 进阶: proxy, reflect
    源码https://github.com/webabcd/TypeScriptDemo作者webabcd兼收并蓄TypeScript-进阶:proxy,reflect示例如下:advanced\proxy_reflect.ts{//Proxy-代理（拦截目标对象的属性操作和函数操作）lettarget={name:'webabcd',age:40,......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99