首页 > 其他分享 >模板大集合

模板大集合

时间：2024-07-10 12:34:35浏览次数：14  
标签：rs int sum ls 集合 救济粮 typ 模板

模板合集

[Vani有约会] 雨天的尾巴 /【模板】线段树合并

题面：

题目背景

深绘里一直很讨厌雨天。

灼热的天气穿透了前半个夏天，后来一场大雨和随之而来的洪水，浇灭了一切。

虽然深绘里家乡的小村落对洪水有着顽固的抵抗力，但也倒了几座老房子，几棵老树被连根拔起，以及田地里的粮食被弄得一片狼藉。

无奈的深绘里和村民们只好等待救济粮来维生。

不过救济粮的发放方式很特别。

题目描述

首先村落里的一共有 \(n\) 座房屋，并形成一个树状结构。然后救济粮分 \(m\) 次发放，每次选择两个房屋 \((x, y)\)，然后对于 \(x\) 到 \(y\) 的路径上（含 \(x\) 和 \(y\)）每座房子里发放一袋 \(z\) 类型的救济粮。

然后深绘里想知道，当所有的救济粮发放完毕后，每座房子里存放的最多的是哪种救济粮。

输入格式

输入的第一行是两个用空格隔开的正整数，分别代表房屋的个数 \(n\) 和救济粮发放的次数 \(m\)。

第 \(2\) 到 第 \(n\) 行，每行有两个用空格隔开的整数 \(a, b\)，代表存在一条连接房屋 \(a\) 和 \(b\) 的边。

第 \((n + 1)\) 到第 \((n + m)\) 行，每行有三个用空格隔开的整数 \(x, y, z\)，代表一次救济粮的发放是从 \(x\) 到 \(y\) 路径上的每栋房子发放了一袋 \(z\) 类型的救济>粮。

输出格式

输出 \(n\) 行，每行一个整数，第 \(i\) 行的整数代表 \(i\) 号房屋存放最多的救济粮的种类，如果有多种救济粮都是存放最多的，输出种类编号最小的一种。

如果某座房屋没有救济粮，则输出 \(0\)。

样例 #1
样例输入 #1
5 3
1 2
3 1
3 4
5 3
2 3 3
1 5 2
3 3 3
样例输出 #1
2
3
3
0
2
提示
  • 对于 \(20\%\) 的数据，保证 \(n, m \leq 100\)。
  • 对于 \(50\%\) 的数据，保证 \(n, m \leq 2 \times 10^3\)。
  • 对于 \(100\%\) 测试数据，保证 \(1 \leq n, m \leq 10^5\)，\(1 \leq a,b,x,y \leq n\)，\(1 \leq z \leq 10^5\)。

线段树合并：即将大量权值线段树合并到一颗线段树上

本题作为板子却出的非常巧妙，让树上差分和线段树合并巧妙结合起来

因为在线段树合并的过程就是 自下而上 的，这个是结合树上差分的重要条件

对于题目中的路径修改，只需要在 \(x、y\) 处 的线段树 \(z\) 位置 \(+1\)，在 \(lca(x,y)\) 和 \(fa_{lca(x,y)}\) 处的线段树 \(z\) 位置 \(-1\) 即可

树剖求 \(LCA\):

int n,m,head[N],nxt[N<<1],to[N<<1],cnt;

void init(){memset(head,-1,sizeof(head));}

void add(int u,int v){
	nxt[cnt] = head[u];
	to[cnt] = v;
	head[u] = cnt++;
}

int dep[N],fa[N],son[N],top[N],siz[N];

void dfs1(int x,int f) {
	siz[x] = 1;
	fa[x] = f;
	dep[x] = dep[f] + 1;
	for(int i = head[x];~i;i = nxt[i]) {
		int y = to[i];
		if(y ^ f) {
			dfs1(y,x);
			siz[x] += siz[y];
			if(siz[son[x]] < siz[y]) son[x] = y;
		}
	}
}

void dfs2(int x,int topx) {
	 top[x] = topx;
	 if(!son[x]) return;
	 dfs2(son[x],topx);
	 for(int i = head[x];~i;i = nxt[i]) {
	 	int y = to[i];
	 	if(y ^ fa[x] && y ^ son[x]) dfs2(y,y);
	 }
}


int LCA(int x,int y) {
	while(top[x] ^ top[y]) {
		if(dep[top[x]] < dep[top[y]]) swap(x,y);
		x = fa[top[x]];
	}
	return dep[x] < dep[y] ? x : y;
}

动态开点线段树：

int root[N],tot;
int ls[N * 50],rs[N * 50],sum[N*50],typ[N*50],ans[N];

#define mid ((pl + pr) >> 1)

void push_up(int p) {
	if(sum[ls[p]] >= sum[rs[p]]) {
		sum[p] = sum[ls[p]];
		typ[p] = typ[ls[p]];
	}else {
		sum[p] = sum[rs[p]];
		typ[p] = typ[rs[p]];
	}
}

void update(int &p,int pl,int pr,int k,int d) {
	if(!p) p = ++tot;
	if(pl == pr){sum[p] += d;typ[p] = k;return;}
	if(k <= mid) update(ls[p],pl,mid,k,d);
	else update(rs[p],mid+1,pr,k,d);
	push_up(p); 
}

 

接下来是合并环节：

首先，如果一个位置只在两颗线段树之一中存在，那么直接接在合并的线段树上

if(!x || !y) return x + y;

如果，访问到同一个叶子节点，参数合并

 if(pl == pr) {sum[x] += sum[y];return x;}

在遍历过程中，更新节点 \(p\) 的 \(ls\) 和 \(rs\)

ls[x] = merge(ls[x],ls[y],pl,mid);
rs[x] = merge(rs[x],rs[y],mid+1,pr);

将新的节点 \(x\) 进行整合 \(ls、rs\) 的答案

push_up(x);

最后，将 \(x\) 节点返回，作为父亲节点的左或右孩子

return x;

所以，合并函数为：

int merge(int x,int y,int pl,int pr) {
	if(!x || !y) return x + y;
	if(pl == pr) {sum[x] += sum[y];return x;}
	ls[x] = merge(ls[x],ls[y],pl,mid);
	rs[x] = merge(rs[x],rs[y],mid+1,pr);
	push_up(x);
	return x;
}

 

递归合并的过程没什么好说的，遍历就可以了

void dfs3(int x,int f) {
	for(int i = head[x];~i;i = nxt[i]) {
		int y = to[i];
		if(y ^ f) { 
			dfs3(y,x);
			root[x] = merge(root[x],root[y],1,N);
		}
	}
	ans[x] = sum[root[x]] ? typ[root[x]] : 0;
}

AC-code:

#include<bits/stdc++.h>
using namespace std;

int rd() {
	int x = 0, w = 1;
	char ch = 0;
	while (ch < '0' || ch > '9') {
		if (ch == '-') w = -1;
		ch = getchar();
	}
	while (ch >= '0' && ch <= '9') {
		x = x * 10 + (ch - '0');
		ch = getchar();
	}
	return x * w;
}

void wt(int x) {
	static int sta[35];
	int f = 1;
	if(x < 0) f = -1,x *= f;
	int top = 0;
	do {
		sta[top++] = x % 10, x /= 10;
	} while (x);
	if(f == -1) putchar('-');
	while (top) putchar(sta[--top] + 48);
}

const int N = 1e5+5;

int n,m,head[N],nxt[N<<1],to[N<<1],cnt;

void init(){memset(head,-1,sizeof(head));}

void add(int u,int v){
	nxt[cnt] = head[u];
	to[cnt] = v;
	head[u] = cnt++;
}

int dep[N],fa[N],son[N],top[N],siz[N];

void dfs1(int x,int f) {
	siz[x] = 1;
	fa[x] = f;
	dep[x] = dep[f] + 1;
	for(int i = head[x];~i;i = nxt[i]) {
		int y = to[i];
		if(y ^ f) {
			dfs1(y,x);
			siz[x] += siz[y];
			if(siz[son[x]] < siz[y]) son[x] = y;
		}
	}
}

void dfs2(int x,int topx) {
	 top[x] = topx;
	 if(!son[x]) return;
	 dfs2(son[x],topx);
	 for(int i = head[x];~i;i = nxt[i]) {
	 	int y = to[i];
	 	if(y ^ fa[x] && y ^ son[x]) dfs2(y,y);
	 }
}


int LCA(int x,int y) {
	while(top[x] ^ top[y]) {
		if(dep[top[x]] < dep[top[y]]) swap(x,y);
		x = fa[top[x]];
	}
	return dep[x] < dep[y] ? x : y;
}

int root[N],tot;
int ls[N * 50],rs[N * 50],sum[N*50],typ[N*50],ans[N];

#define mid ((pl + pr) >> 1)

void push_up(int p) {
	if(sum[ls[p]] >= sum[rs[p]]) {
		sum[p] = sum[ls[p]];
		typ[p] = typ[ls[p]];
	}else {
		sum[p] = sum[rs[p]];
		typ[p] = typ[rs[p]];
	}
}

void update(int &p,int pl,int pr,int k,int d) {
	if(!p) p = ++tot;
	if(pl == pr){sum[p] += d;typ[p] = k;return;}
	if(k <= mid) update(ls[p],pl,mid,k,d);
	else update(rs[p],mid+1,pr,k,d);
	push_up(p); 
} 

int merge(int x,int y,int pl,int pr) {
	if(!x || !y) return x + y;
	if(pl == pr) {sum[x] += sum[y];return x;}
	ls[x] = merge(ls[x],ls[y],pl,mid);
	rs[x] = merge(rs[x],rs[y],mid+1,pr);
	push_up(x);
	return x;
}

void dfs3(int x,int f) {
	for(int i = head[x];~i;i = nxt[i]) {
		int y = to[i];
		if(y ^ f) { 
			dfs3(y,x);
			root[x] = merge(root[x],root[y],1,N);
		}
	}
	ans[x] = sum[root[x]] ? typ[root[x]] : 0;
}

signed main(){
	init();
	n = rd(),m = rd();

	for(int i = 1,u,v;i<n;i++) {
		add(u = rd(),v = rd());
		add(v,u);
	}
	dfs1(1,0);
	dfs2(1,1);
	while(m--){
		int a = rd(),b = rd(),z = rd();
		update(root[a],1,N,z,1);
		update(root[b],1,N,z,1);
		int t = LCA(a,b);
		update(root[t],1,N,z,-1);
		update(root[fa[t]],1,N,z,-1);
	}
	dfs3(1,0);

	for(int i = 1;i<=n;i++) {wt(ans[i]);putchar('\n');}

	return 0;
}

标签：rs,int,sum,ls,集合,救济粮,typ,模板
From： https://www.cnblogs.com/WG-MingJunYi/p/18293614

相关文章

  • 【模板】多项式乘法逆
    变量的值被莫名修改，往往是因为地址的传递导致两个变量绑定在了一起怎样搜索替换double为longdouble呢？或许可以先转化为longDouble，再转化为longdouble点击查看代码#include<bits/stdc++.h>usingnamespacestd;longlonga[300005],tmp[300005];longlongf0[300005],......
  • 集合幂级数
    集合幂级数从\(2^U\rightarrowR\)​的映射加法乘法\(h=f\cdotg=\sum\limits_{L\in2^U}\sum\limits_{R\in2^U}f_Lg_Rx^{L\oplusR}\)类比乘法，其中\(\oplus\)​需要满足交换律，结合律高维前缀和的dp解释设\(f_{S,i}\)表示考虑\(S\)的子集的后\(i\)位，前\(|S|-i......
  • 【转】-并发下的集合
    高并发下的Java数据结构(List、Set、Map、Queue)本文转载至​薛勤的博客​的​高并发下的Java数据结构(List、Set、Map、Queue)由于并行程序与串行程序的不同特点，适用于串行程序的一些数据结构可能无法直接在并发环境下正常工作，这是因为这些数据结构不是线程安全的。本节将着重......
  • 回收站清空恢复？其实很简单！6种方法集合任你选！
    在我们的日常生活和工作中，误删文件的情况时有发生，尤其是当我们匆忙操作或者误操作时，更容易将重要文件不小心清空到回收站。回收站清空恢复看似复杂，实则方法多样，只需掌握正确的技巧，就能轻松恢复重要文件。本文将为大家介绍六种行之有效的方法，其中包括使用广受好评的嗨格式数据恢......
  • SPFA算法模板和判断负环
    851.spfa求最短路-AcWing题库852.spfa判断负环-AcWing题库#include<bits/stdc++.h>usingnamespacestd;constintN=1e5+10;intn,m,k;inth[N],e[N],idx,w[N],ne[N];intq[N],tt=-1,hh=0;voidadd(inta,intb,intc){ e[idx]=b; ne[idx]=h[a]; w[idx]=c;......
  • Java 中的泛型 集合(List,Set) Map
    泛型集合(List,Set)Map泛型泛型的本质是参数化类型,即允许在编译时对集合进行类型检查,从而避免安全问题,提高代码的复用性泛型的具体定义与作用定义:泛型是一种在编译阶段进行类型检查的机制,它允许在类,方法,接口后通过<>来声明类型参数.这些参数在编译时会被具体的类......
  • NetCore 模板引擎
    HTML模板<!DOCTYPEhtml><htmlxmlns="http://www.w3.org/1999/xhtml"><head><metahttp-equiv="Content-Type"content="text/html;charset=utf-8"/><title>@Model.Title</title></hea......
  • DataTable 与 泛型集合List<T>相互转换
    List转DataTablepublicstaticDataTableToDataTable<T>(thisList<T>list){DataTableresult=newDataTable();List<PropertyInfo>pList=newList<PropertyInfo>();Typetype=typeof(T);Array......
  • java集合笔记分享
    集合 前言集合：集合是java中提供的一种容器，可以用来存储多个数据。集合和数组既然都是容器，它们有啥区别呢？集合和数组的区别：   数组的长度是固定的。集合的长度是可变的。   数组中存储的是同一类型的元素，可以存储基本数据类型值。集合存储的都是对象。而且对象的......
  • G64【模板】线性基 贪心法 P3812 最大异或和
    视频链接：G64【模板】线性基贪心法P3812最大异或和_哔哩哔哩_bilibili   P3812【模板】线性基-洛谷|计算机科学教育新生态(luogu.com.cn)//线性基O(63*n)#include<iostream>#include<cstring>#include<algorithm>usingnamespacestd;typedeflong......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99