首页 > 其他分享 >几个板子

几个板子

时间:2023-04-16 11:14:41浏览次数:30  
标签:return val 几个 siz void tr 板子 int

FHQ Treap
普通平衡树

struct treap
{
	int l, r, siz, dat, val;
} tr[N];
int idx, rt;
int get_new(int val)
{
	tr[++ idx].val = val;
	tr[idx].dat = rand();
	tr[idx].siz = 1;
	return idx;
}
void pushup(int u)
{
	tr[u].siz = tr[tr[u].l].siz + tr[tr[u].r].siz + 1;
}
void split(int u, int v, int &x, int &y)
{
	if(!u) x = y = 0;
	else
	{
		if(tr[u].val <= v) x = u, split(tr[x].r, v, tr[x].r, y);
		else y = u, split(tr[y].l, v, x, tr[y].l);
		pushup(u);
	}
}
int merge(int x, int y)
{
	if(!x || !y) return x + y;
	if(tr[x].dat < tr[y].dat)
	{
		tr[x].r = merge(tr[x].r, y);
		pushup(x);
		return x;
	}
	else
	{
		tr[y].l = merge(x, tr[y].l);
		pushup(y);
		return y;
	}
}
void insert(int val)
{
	int x, y, z;
	split(rt, val, x, y);
	z = get_new(val);
	rt = merge(merge(x, z), y);
}
void remove(int val)
{
	int x, y, z;
	split(rt, val, x, z);
	split(x, val - 1, x, y);
	y = merge(tr[y].l, tr[y].r);
	rt = merge(merge(x, y), z);
}
int get_rk_by_val(int val)
{
	int x, y, res;
	split(rt, val - 1, x, y);
	res = tr[x].siz + 1;
	rt = merge(x, y);
	return res;
}
int get_val_by_rk(int u, int rk)
{
	if(rk <= tr[tr[u].l].siz) return get_val_by_rk(tr[u].l, rk);
	else if(rk == tr[tr[u].l].siz + 1) return tr[u].val;
	return get_val_by_rk(tr[u].r, rk - tr[tr[u].l].siz - 1);
}
int get_pre(int val)
{
	int x, y, res;
	split(rt, val - 1, x, y);
	res = get_val_by_rk(x, tr[x].siz);
	rt = merge(x, y);
	return res;
}
int get_nxt(int val)
{
	int x, y, res;
	split(rt, val, x, y);
	res = get_val_by_rk(y, 1);
	rt = merge(x, y);
	return res;
}

Splay
普通平衡树

int n,idx,root;
struct Splay
{
	int s[2],v,p,size;
	int cnt;
	void init(int _v,int _p)
	{
		v=_v,p=_p;
		size=cnt=1;
	}
}tr[N];
void push_up(int x)
{
	tr[x].size=tr[tr[x].s[0]].size+tr[tr[x].s[1]].size+tr[x].cnt;
}
void rotate(int x)
{
	int y=tr[x].p,z=tr[y].p;
	int k=tr[y].s[1]==x;
	tr[z].s[tr[z].s[1]==y]=x,tr[x].p=z;
	tr[y].s[k]=tr[x].s[k^1],tr[tr[x].s[k^1]].p=y;
	tr[x].s[k^1]=y,tr[y].p=x;
	push_up(y),push_up(x);
}
void splay(int x,int k)
{
	while(tr[x].p!=k)
	{
		int y=tr[x].p,z=tr[y].p;
		if(z!=k)
			if((tr[z].s[1]==y)^(tr[y].s[1]==x)) rotate(x);
			else rotate(y);
		rotate(x);
	}
	if(!k) root=x;
}
void find(int v)
{
	int x=root;
	while(tr[x].s[v>tr[x].v]&&v!=tr[x].v)
		x=tr[x].s[v>tr[x].v];
	splay(x,0);
}
int get_prev(int v)
{
	find(v);
	int x=root;
	if(tr[x].v<v) return x;
	x=tr[x].s[0];
	while(tr[x].s[1]) 
		x=tr[x].s[1];
	return x;
}
int get_next(int v)
{
	find(v);
	int x=root;
	if(tr[x].v>v) return x;
	x=tr[x].s[1];
	while(tr[x].s[0]) 
		x=tr[x].s[0];
	return x;
}
void del(int v)
{
	int prev=get_prev(v),next=get_next(v);
	splay(prev,0),splay(next,prev);
	int son=tr[next].s[0];
	if(tr[son].cnt>1)
		tr[son].cnt--,splay(son,0);
	else
		tr[next].s[0]=0,splay(next,0);
}
int get_kth(int k)
{
	int u=root;
	while(u)
	{
		if(tr[tr[u].s[0]].size>=k) u=tr[u].s[0];
		else if(tr[tr[u].s[0]].size+tr[u].cnt>=k)
		{
			splay(u,0);
			return tr[u].v;
		} 
		else k-=tr[tr[u].s[0]].size+tr[u].cnt,u=tr[u].s[1];
	}
	return -1;
}
void insert(int v)
{
	int u=root,p=0;
	while(u)
	{
		if(tr[u].v==v)
		{
			splay(u,0);
			tr[u].cnt++;
			return;
		}
		p=u;
		u=tr[u].s[v>tr[u].v];
	}
	u=++idx;
	if(p) tr[p].s[v>tr[p].v]=u;
	tr[u].init(v,p);
	splay(u,0);
}

文艺平衡树

int root,idx;
struct Splay
{
	int s[20],size,flag,v,p;
	void init(int _v,int _p)
	{
		v=_v,p=_p;
		size=1;
	}
} tr[N];
void push_up(int x)
{
	tr[x].size=tr[tr[x].s[0]].size+tr[tr[x].s[1]].size+1;
}
void push_down(int x)
{
	if(!tr[x].flag) 
		return;
	swap(tr[x].s[0],tr[x].s[1]);
	tr[tr[x].s[0]].flag^=1;
	tr[tr[x].s[1]].flag^=1;
	tr[x].flag=0;
}
void rotate(int x)
{
	int y=tr[x].p,z=tr[y].p;
	int k=tr[y].s[1]==x;
	tr[z].s[tr[z].s[1]==y]=x,tr[x].p=z;
	tr[y].s[k]=tr[x].s[k^1],tr[tr[x].s[k^1]].p=y;
	tr[x].s[k^1]=y,tr[y].p=x;
	push_up(y);
	push_up(x);
}
void splay(int x,int k)
{
	while(tr[x].p!=k)
	{
		int y=tr[x].p,z=tr[y].p;
		if(z!=k)
			if(tr[y].s[1]==x != tr[z].s[1]==y) rotate(x);
			else rotate(y);
		rotate(x);
	}
	if(!k) root=x;
}
void insert(int v)
{
	int u=root,p=0;
	while(u)
	{
		p=u;
		u=tr[u].s[v>tr[u].v];
	}
	u=++idx;
	if(p) tr[p].s[v>tr[p].v]=u;
	tr[u].init(v,p);
	splay(u,0);
}
int get_kth(int k)
{
	int u=root;
	while(true)
	{
		push_down(u);
		if(tr[tr[u].s[0]].size>=k) u=tr[u].s[0];
		else if(tr[tr[u].s[0]].size+1==k) return u;
		else k-=tr[tr[u].s[0]].size+1,u=tr[u].s[1];
	}
	return -1;
}
void output(int u)
{
	push_down(u);
	if(tr[u].s[0]) 
		output(tr[u].s[0]);
	if(tr[u].v>=1&&tr[u].v<=n) printf("%d ", tr[u].v);
	if(tr[u].s[1]) 
		output(tr[u].s[1]);
}

Treap

struct treap
{
	int l, r;
	int val, dat;
	int cnt, siz;
} tr[N];
int idx, rt;
int get_new(int val)
{
	tr[++ idx].val = val;
	tr[idx].dat = rand();
	tr[idx].siz = tr[idx].cnt = 1;
	return idx;
}
void pushup(int x)
{
	tr[x].siz = tr[tr[x].l].siz + tr[tr[x].r].siz + tr[x].cnt;
}
void zig(int &x)
{
	int y = tr[x].l;
	tr[x].l = tr[y].r, tr[y].r = x, x = y;
	pushup(tr[x].r), pushup(x);
}
void zag(int &x)
{
	int y = tr[x].r;
	tr[x].r = tr[y].l, tr[y].l = x, x = y;
	pushup(tr[x].l), pushup(x);
}
void insert(int &x, int val)
{
	if(x == 0)
	{
		x = get_new(val);
		return;
	}
	if(val == tr[x].val)
	{
		tr[x].cnt ++, pushup(x);
		return;
	}
	if(val < tr[x].val)
	{
		insert(tr[x].l, val);
		if(tr[tr[x].l].dat > tr[x].dat) zig(x);
	}
	else if(val > tr[x].val)
	{
		insert(tr[x].r, val);
		if(tr[tr[x].r].dat > tr[x].dat) zag(x);
	}
	pushup(x);
}
void remove(int &x, int val)
{
	if(x == 0) return;
	if(tr[x].val == val)
	{
		if(tr[x].cnt > 1) 
		{
			tr[x].cnt --;
			pushup(x);
			return;
		}
		if(tr[x].l || tr[x].r)
		{
			if(tr[x].r == 0 || tr[tr[x].l].dat > tr[tr[x].r].dat)
				zig(x), remove(tr[x].r, val);
			else
				zag(x), remove(tr[x].l, val);
			pushup(x);
		}
		else x = 0;
		return;
	}	
	if(val < tr[x].val) remove(tr[x].l, val);
	else remove(tr[x].r, val);
	pushup(x);
}
int get_rk_by_val(int x, int val)
{
	if(x == 0) return 0;
	if(val == tr[x].val) return tr[tr[x].l].siz + 1;
	if(val < tr[x].val) return get_rk_by_val(tr[x].l, val);
	return tr[tr[x].l].siz + tr[x].cnt + get_rk_by_val(tr[x].r, val);
}
int get_val_by_rk(int x, int rk)
{
	if(x == 0) return INF;
	if(tr[tr[x].l].siz >= rk) return get_val_by_rk(tr[x].l, rk);
	if(tr[tr[x].l].siz + tr[x].cnt >= rk) return tr[x].val;
	return get_val_by_rk(tr[x].r, rk - tr[tr[x].l].siz - tr[x].cnt);
}
int get_pre(int x, int val)
{
	if(x == 0) return -INF;
	if(val <= tr[x].val) return get_pre(tr[x].l, val);
	return max(tr[x].val, get_pre(tr[x].r, val)); 
}
int get_nxt(int x, int val)
{
	if(x == 0) return INF;
	if(val >= tr[x].val) return get_nxt(tr[x].r, val);
	return min(tr[x].val, get_nxt(tr[x].l, val));
}

树状数组

struct BIT
{
	int c[N], mx;
	#define lbt(x) x & -x
	void Add(int x, int v)
	{
		for(;x <= mx;x += lbt(x)) c[x] += v;
	}
	int Ask(int x)
	{
		int res = 0;
		for(;x;x -= lbt(x)) res += c[x];
		return res;
	}
} bit;

线段树

struct segment_tree
{
	int l, r, val, tag;
	#define l(x) tr[x].l
	#define r(x) tr[x].r
	#define val(x) tr[x].val
	#define tag(x) tr[x].tag
}tr[N << 2];
void pushup(int x)
{
	val(x) = val(x << 1) + val(x << 1 | 1);
}
void pushdown(int x)
{
	if(!tag(x)) return;
	tag(x << 1) += tag(x);
	val(x << 1) += (r(x << 1) - l(x << 1) + 1) * tag(x);
	tag(x << 1 | 1) += tag(x);
	val(x << 1 | 1) += (r(x << 1 | 1) - l(x << 1 | 1) + 1) * tag(x);
	tag(x) = 0;
}
void build(int l, int r, int x)
{
	l(x) = l, r(x) = r;
	if(l == r)
	{
		val(x) = a[l];
		return;
	}
	int mid = l + r >> 1;
	build(l, mid, x << 1);
	build(mid + 1, r, x << 1 | 1);
	pushup(x);
}
void update(int l, int r, int x, ll v)
{
	if(l <= l(x) && r(x) <= r)
	{
		val(x) += (r(x) - l(x) + 1) * v;
		tag(x) += v;
		return;
	}
	pushdown(x);
	int mid = l(x) + r(x) >> 1;
	if(l <= mid) update(l, r, x << 1, v);
	if(r > mid) update(l, r, x << 1 | 1, v);
	pushup(x);
}
int query(int l, int r, int x)
{
	if(l <= l(x) && r(x) <= r) return val(x);
	pushdown(x);
	int mid = l(x) + r(x) >> 1, res = 0;
	if(l <= mid) res += query(l, r, x << 1);
	if(r > mid) res += query(l, r, x << 1 | 1);
	return res;
}

树链剖分

void dfs1(int u, int fath)  //处理fa,dep,siz,son
{
	fa[u] = fath;
	dep[u] = dep[fath] + 1;
	siz[u] = 1;
	for(auto v:e[u])
	{
		if(v == fath) continue;
		dfs1(v, u);
		siz[u] += siz[v];
		if(siz[v] > siz[son[u]])
			son[u] = v;
	}
}
void dfs2(int u, int fst)
{
	id[u] = ++ idx;
	a[idx] = w[u];值
	top[u] = fst;
	if(!son[u]) return;
	dfs2(son[u], fst);
	for(auto v:e[u])
	{
		if(v == fa[u] || v == son[u]) continue;
		dfs2(v, v);
	}
}

快速幂

int Pow(int a, int b)
{
	int res = 1;
	for(;b;a *= a, b >>= 1) if(b & 1) res *= a; 
	return res;
}

ST表

for(int j = 1;(1 << j) <= n;j ++)
		for(int i = 1;i + (1 << j) - 1<= n;i ++)
			f[i][j] = max(f[i][j - 1], f[i + (1 << (j - 1))][j - 1]);

dijkstra

void duijkstra()
{
	for(int i = 1;i <= n;i ++) dist[i] = INF, st[i] = false;
	priority_queue<PII, vector<PII>, greater<PII> > q;
	dist[s] = 0;
	q.push({0, s});
	while(q.size())
	{
		int u = q.top().se;
		q.pop();
		if(st[u]) continue;
		st[u] = true;
		for(int i = h[u];i;i = nxt[i])
		{
			int v = to[i], w = val[i];
			if(dist[v] > dist[u] + w)
			{
				dist[v] = dist[u] + w;
				q.push({dist[v], v});
			}
		}
	}
}

加边

int h[N], nxt[M << 1], to[M << 1], val[M << 1], cnt;
void add(int u, int v, int w)
{
	to[++ cnt] = v, val[cnt] = w, nxt[cnt] = h[u], h[u] = cnt;
}
int h[N], nxt[M << 1], to[M << 1], cnt;
void add(int u, int v)
{
	to[++ cnt] = v, nxt[cnt] = h[u], h[u] = cnt;
}

LCA

void dfs(int u, int fath)
{
    dep[u] = dep[fath] + 1, fa[u][0] = fath;
    for(int i = 1;i <= lg[dep[u]];i ++) fa[u][i] = fa[fa[u][i - 1]][i - 1];
    for(int i = head[u];i;i = nxt[i])
    {
        int v = to[i];
        if(v == fath) continue;
        dfs(v, u);
    }
}
int lca(int u, int v)
{
    if(dep[u] < dep[v]) swap(u, v);
    while(dep[u] > dep[v]) u = fa[u][lg[dep[u] - dep[v]]];
    if(u == v) return u;
    for(int k = lg[dep[u]];k >= 0;k --)
        if(fa[u][k] != fa[v][k]) u = fa[u][k], v = fa[v][k];
    return fa[u][0];
}

DSU

int fa[N];
void dsu_clear()
{
    for(int i = 1;i <= n;i ++) fa[i] = i;
}
int find(int x)
{
	if(fa[x] == x) return x;
	return fa[x] = find(fa[x]);
}
void merge(int x, int y)
{
	fa[find(x)] = find(y);
}

最小生成树

sort(e + 1, e + 1 + m);
	ll res = 0;
	for(int i = 1;i <= m;i ++)
	{
		int u = find(e[i].u), v = find(e[i].v);
		if(u == v) continue;
		res += e[i].w;
		merge(u, v);
	}

Floyd

for(int i = 1;i <= n;i ++) f[i][i] = 0;
	for(int k = 1;k <= n;k ++)
		for(int i = 1;i <= n;i ++)
			for(int j = 1;j <= n;j ++) 
				f[i][j] = min(f[i][j], f[i][k] + f[k][j]);

矩阵快速幂

struct matrix
{
	ll c[105][105];
} A;
ll n, k;
matrix operator *(const matrix &a, const matrix &b)
{
	matrix c;
	for(int i = 1;i <= n;i ++)
		for(int j = 1;j <= n;j ++) c.c[i][j] = 0;
	for(int i = 1;i <= n;i ++)
		for(int j = 1;j <= n;j ++)
			for(int k = 1;k <= n;k ++)
				c.c[i][j] = (c.c[i][j] + a.c[i][k] * b.c[k][j]) % mod;
	return c;
}
matrix qpow(matrix a, ll b)
{
	matrix res;
	for(int i = 1;i <= n;i ++) res.c[i][i] = 1;
	for(;b;a = a * a, b >>= 1)if(b & 1) res = res * a;
	return res;
}

标签:return,val,几个,siz,void,tr,板子,int
From: https://www.cnblogs.com/Svemit/p/17322675.html

相关文章

  • 少有人知道的几个工具网站,值得收藏!-搜嗖工具箱
    Behancehttps://www.behance.net/Behance一个全球最大的创意社区,它为设计师、艺术家、摄影师、插画家等创意人才提供了一个展示自己作品,获取灵感和反馈的平台。Behance用户群体庞大,拥有超过1亿的访问量和超过1000万的注册用户。你可以在此网站中上传包括平面设计、UI设计、插......
  • 电商购物系统开发的正确步骤是什么?这几个步骤不能忘
     毫不夸张地说,电商购物已经成为当代人们主要的购物方式。在这样的时代背景下,越来越多的企业商家争相开发一个电商购物系统,试图实现盈利。那么电商购物系统开发的正确步骤是什么?下面名锐讯动为大家讲述这几个步骤不能忘。 1.分析市场需求。前面我们说过开发一个电商购物系统的......
  • 在页面中添加侧边栏导航及几个颜色搭配的网站
    先调出主题的侧边栏,然后使用小工具在侧边栏里添加导航小工具,选择创建的菜单。颜色搭配网站HappyHues-Curatedcolorsincontext.https://color.adobe.com/zh/create/color-wheelColorSpace-ColorPalettesGeneratorandColorGradientTool(mycolor.space) ......
  • JSON.stringify()的几个场景
    循环引用使用JSON.stringify()时,遇到循环引用的时候,会抛出错误TypeError:ConvertingcircularstructuretoJSON,如果需要强行转成字符串的话,需要利用到该方法的第二个参数。主要思路其实就是将循环引用的部分替换成某个标识,等到解析的时候去替换掉,就可以拿到原来的循环引用的......
  • 线段树区间和,区间修改,区间查询板子
    #include<bits/stdc++.h>usingnamespacestd;usingLL=longlong;#definelson(nd<<1)#definerson(nd<<1|1)#definemid(l+r>>1)constintN=1e5+5;intsum[N<<2],lazy[N<<2];inta[N];voidbuild(intnd,in......
  • 【AGC】崩溃服务数据上报常见的几个问题
    最近开发者使用崩溃服务遇到的一些数据异常问题,我在这里汇总一下,以后遇到相似的问题可以以此为参考。 【问题描述1】iOS崩溃数据“按用户搜索”页,“过去7天”是有数据的,但“统计”页没有。​​【解决方案】查询了后台上报日志,发现没有上报应用的启动事件,只上报了$HA_ERRO......
  • 在图片上编辑文字的软件分享!这个几个很不错!​
    在图片上编辑文字的软件!图片上编辑文字指的是在一张图片上添加或编辑文字的过程。这个过程可以使用各种软件和工具来完成,用户可以选择不同的字体、字号、颜色、对齐方式等样式设置,并将文字添加到图片上的指定位置。这个过程通常用于创建海报、广告、卡片、漫画等需要文字和图片结合......
  • vue的几个记录
    1.父组件传递子组卷数组参数props:{boxData:{type:Array,default:()=>[],//重点},2.要实现父组件传递子组卷的参数动态更新(父-》子-》子,也只需要在最后一个子组件监听即可。)需要用到监听器watch:{//监听父组件传递的参数,以动态更新boxDa......
  • 【230409-6】由数字1,2,3,4,5组成,没有重复数字的五位数,其中小于50000的偶数共有几个?
    ......
  • 小程序商城定制开发要实行哪些举动?这几个举动很有效
     为了让小程序商城更加符合自身的发展需求,不少企业商家会选择找一个开发商帮助自己定制开发。这就产生一个问题,小程序商城定制开发要实行哪些举动?针对这个问题,下面名锐迅动为大家介绍这几个举动很有效。 1.确定功能风格。既然是定制开发一个小程序商城,那么就不希望自己的小程......