首页 > 其他分享 >【模板】数据结构

【模板】数据结构

时间：2024-08-17 22:49:08浏览次数：11  
标签：ch int void len bk ls 数据结构 模板

数据结构

  • 权值 BIT 上二分
struct {
    int n,t[N];
	int kth(int k) {
		int p = 0;
        rFor(i,__lg(n),0) if( p+(1<<i) < n && k > t[p+(1<<i)] ) p += 1<<i, k -= t[p];
		return p+1;
	}
} ;

  • zkw 线段树

  • 李超线段树

  • 线段树合并，分裂

  • 可持久化 \(01\)Trie

值域 \([0,2^{30})\)

struct {
	int ind,rt[N],ch[N*31][2],siz[N*31];
	void ins(int u,int v,int x) {
		u = rt[u], v = rt[v] = ++ind;
		rFor(i,29,0) {
			bool y = x>>i&1;
			ch[v][!y] = ch[u][!y], u = ch[u][y], v = ch[v][y] = ++ind,
			siz[v] = siz[u] + 1;
		}
	}
	int qry(int u,int v,int x) {
		u = rt[u], v = rt[v];
		int res = 0;
		for(int i = 1<<29; i; i >>= 1) {
			bool y = ~x&i;
			if( siz[ch[u][y]] < siz[ch[v][y]] ) res |= i, u = ch[u][y], v = ch[v][y];
			else u = ch[u][!y], v = ch[v][!y];
		}
		return res;
	}
} ;
  • 笛卡尔树

升序 BST 以 \(i\) 为权值，小根堆以 \(a[i]\) 为权值

void bld() {
	For(i,1,n) {
		int tmp = tp;
		while( tp && a[i] < a[stk[tp]] ) --tp;
		if( tp ) ch[stk[tp]][1] = i;
		if( tp < tmp ) ch[i][0] = stk[tp+1];
		stk[++tp] = i;
	}
}
  • 可持久化文艺平衡树

空间限制 \(256\)MB

// LG5586 [P5350] 序列 (加强版)
#define ls(u) t[u].ch[0]
#define rs(u) t[u].ch[1]
const int N = 3e5+5, M = 5e6;
int ind,rt,n,a[N],len[N];
struct Node { int ch[2],siz,len; mint val,sum,add; bool rev; } t[M+N];
int node(int len,mint x)
	{ return t[++ind] = {0,0,len,len,x,len*x,0,0}, ind; }
int node(const Node &x){ return t[++ind] = x, ind; }
void up(int u) {
	t[u].siz = t[ls(u)].siz + t[rs(u)].siz + t[u].len,
	t[u].sum = t[ls(u)].sum + t[rs(u)].sum + t[u].len*t[u].val;
}
void down(int u,mint x,bool y) {
	if( x.x ) t[u].val += x, t[u].add += x, t[u].sum += t[u].siz * x;
	if( y ) t[u].rev ^= y, swap(ls(u),rs(u));
}
void down(int u) { if( t[u].add.x || t[u].rev ) {
	if( ls(u) ) down( ls(u)=node(t[ls(u)]) ,t[u].add,t[u].rev);
	if( rs(u) ) down( rs(u)=node(t[rs(u)]) ,t[u].add,t[u].rev);
	t[u].add = t[u].rev = 0;
}}
void dfs(int u) {
	down(u);
	if( ls(u) ) dfs(ls(u));
	if( n && a[n] == t[u].val.x ) len[n] += t[u].len;
	else a[++n] = t[u].val.x, len[n] = t[u].len;
	if( rs(u) ) dfs(rs(u));
}
int bld(int l=1,int r=n) {
	if( l > r ) return 0;
	int mid = l+r>>1, u = node(len[mid],a[mid]);
	return ls(u) = bld(l,mid-1), rs(u) = bld(mid+1,r), up(u), u;
}
void rbld() { n = 0, dfs(rt), ind = 0, rt = bld(); }
void split(int u,int k,int &l,int &r) {
	if( !u ) { l = r = 0; return; }
	down(u);
	if( t[ls(u)].siz < k && k < t[ls(u)].siz+t[u].len ) {
		int mid = k-t[ls(u)].siz, v = node(t[u]);
		t[v].len = t[u].len-mid, t[u].len = mid;
		ls(v) = 0, rs(u) = v, up(v), up(u);
	}
	if( k <= t[ls(u)].siz ) r = node(t[u]), split(ls(r),k,l,ls(r)), up(r);
	else l = node(t[u]), split(rs(l),k-t[ls(l)].siz-t[l].len,rs(l),r), up(l);
}
int merge(int l,int r) {
	if( !l || !r ) return l | r;
	int u;
	if( mt()%(t[l].siz+t[r].siz) < t[l].siz )
		down(u=node(t[l])), rs(u) = merge(rs(u),r);
	else down(u=node(t[r])), ls(u) = merge(l,ls(u));
	return up(u), u;
}
mint sum(int l,int r) { // ask sum of [l,r]
	int a,b,c; split(rt,r,b,c), split(b,l-1,a,b);
	mint res = t[b].sum;
	rt = merge(merge(a,b),c);
	return res;
}
void cov(int l,int r,int x) { // let [l,r] = x
	int a,b,c; split(rt,r,b,c), split(b,l-1,a,b);
	rt = merge(merge(a,node(r-l+1,x)),c);
}
void add(int l,int r,int x) { // let [l,r] += x
	int a,b,c; split(rt,r,b,c), split(b,l-1,a,b);
	down(b,x,0);
	rt = merge(merge(a,b),c);
}
void copy(int l1,int r1,int l2,int r2) { // let [l2,r2] = [l1,r1]
	int a,b,c,d,e; bool flg = 0;
	if( l1 > l2 ) swap(l1,l2), swap(r1,r2), flg = 1;
	split(rt,r2,d,e), split(d,l2-1,c,d), split(c,r1,b,c), split(b,l1-1,a,b);
	rt = merge(merge(merge(merge(a,!flg?b:d),c),!flg?b:d),e);
}
void swap(int l1,int r1,int l2,int r2) { // swap [l1,r1] and [l2,r2]
	if( l1 > l2 ) swap(l1,l2), swap(r1,r2);
	int a,b,c,d,e;
	split(rt,r2,d,e), split(d,l2-1,c,d), split(c,r1,b,c), split(b,l1-1,a,b);
	rt = merge(merge(merge(merge(a,d),c),b),e);
}
void rev(int l,int r) { // reverse [l,r]
	int a,b,c; split(rt,r,b,c), split(b,l-1,a,b);
	down(b,0,1);
	rt = merge(merge(a,b),c);
}
void dbg() {
	n = 0, dfs(rt);
	For(i,1,n, p = 1) {
		if( len[i] > 1 ) cerr<<"["<<p<<","<<p+len[i]-1<<"]:";
		cerr<<a[i]<<(i<n?' ':'\n');
		p += len[i];
	}
}
signed main() {
	cin>>n>>m; For(i,1,n) cin>>a[i], len[i] = 1;
	rt = bld();
	while( m-- ) {
		
		if( ind >= M ) rbld();
//		dbg();
	}
	n = 0, dfs(rt); For(i,1,n) For(j,1,len[i]) cout<<a[i]<<" ";
}

  • KDT

  • LCT

#define ls(u) t[u].ch[0]
#define rs(u) t[u].ch[1]
struct {
	struct Node { int fa,ch[2]; bool rev; } t[];
	void rev(int u) { swap(ls(u),rs(u)), t[u].rev ^= 1; }
	void down(int u) { if( t[u].rev ) rev(ls(u)), rev(rs(u)), t[u].rev = 0; }
	bool nrt(int u) { return ls(t[u].fa)==u || rs(t[u].fa)==u; }
	bool wh(int u) { return rs(t[u].fa)==u; }
	void rotate(int x) {
		int y = t[x].fa, z = t[y].fa, k = wh(x), w = t[x].ch[!k];
		if( nrt(y) ) t[z].ch[wh(y)] = x; t[x].ch[!k] = y, t[y].ch[k] = w;
		t[w].fa = y, t[y].fa = x, t[x].fa = z;
	}
	void splay(int u) {
		static int tp,stk[N];
		for(int v = stk[tp=1] = u; nrt(v); stk[++tp] = v = t[v].fa);
		while( tp ) down(stk[tp--]);
		for(int fa; fa = t[u].fa, nrt(u); rotate(u))
			if( nrt(fa) ) rotate(wh(fa)==wh(u)?fa:u);
	}
	void access(int x) {
		for(int u = x, v = 0; u; u = t[v=u].fa) splay(u), rs(u) = v;
		splay(x);
	}
	void mkrt(int u) { access(u), rev(u); }
	int fdrt(int u) {
		access(u);
		while( ls(u) ) down(u), u = ls(u);
		return splay(u), u;
	}
	void split(int u,int v) { mkrt(u), access(v); }
	void link(int u,int v) { mkrt(u), t[u].fa = v; }
	void cut(int u,int v) { split(u,v), t[u].fa = ls(v) = 0; }
} ;
  • 珂朵莉树
struct CT {
	int l,r;
	mutable int val;
	CT(int l=0,int r=0,int val=0):l(l),r(r),val(val){}
	bool operator < (const CT &rhs) const { return l < rhs.l; }
}; set<CT> ct;
auto split(int p) {
	auto it = --ct.upper_bound({p});
	if( it->l == p ) return it;
	int l = it->l, r = it->r, x = it->val;
	ct.erase(it), ct.emplace(l,p-1,x);
	return ct.emplace(p,r,x).fi;
}
void assign(int l,int r,int x) {
	auto itr = split(r+1), itl = split(l);
	// if( itr != ct.end() && x == itr->val ) r = (itr++)->r;
	// if( itl != ct.begin() && x == prev(itl)->val) l = (--itl)->l;
	ct.erase(itl,itr), ct.emplace(l,r,x);
}
  • 压位 trie

值域 \([0,2^{20})\)

// bzoj3685 普通van Emde Boas树
#define ctz(x) (uLL)__builtin_ctzll(x)
#define clz(x) (uLL)__builtin_clzll(x)
struct Trie {
	uLL *t[4];
	Trie() {
		t[0] = new uLL[1<<14](), t[1] = new uLL[1<<8](),
		t[2] = new uLL[1<<2](), t[3] = new uLL[1<<0]();
	}
	void ins(int x) {
		Rep(i,0,4) {
			uLL &u = t[i][x>>(i+1)*6], e = 1ull<<(x>>i*6&63);
			if( u & e ) return; u |= e;
		}
	}
	void ers(int x)
        { Rep(i,0,4) if( t[i][x>>(i+1)*6] &= ~(1ull<<(x>>i*6&63)) ) return; }
	int min() {
		if( !t[3][0] ) return -1;
		int u = 0; rFor(i,3,0) u |= ctz(t[i][u>>(i+1)*6]) << i*6;
		return u;
	}
	int max() {
		if( !t[3][0] ) return -1;
		int u = 0; rFor(i,3,0) u |= 63-clz(t[i][u>>(i+1)*6]) << i*6;
		return u;
	}
	int suf(int x) {
		Rep(i,0,4) {
			int e = x>>i*6&63; uLL u = t[i][x>>(i+1)*6];
			if( u>>e > 1 ) {
				int res = x >> (i+1)*6 << (i+1)*6;
				res |= ctz(u>>e+1)+e+1 << i*6;
				rFor(j,i-1,0) res |= ctz(t[j][res>>(j+1)*6]) << j*6;
				return res;
			}
		}
		return -1;
	}
	int pre(int x) {
		Rep(i,0,4) {
			int e = x>>i*6&63; uLL u = t[i][x>>(i+1)*6];
			if( u & (1ull<<e)-1 ) {
				int res = x >> (i+1)*6 << (i+1)*6;
				res |= 63-clz(u&(1ull<<e)-1) << i*6;
				rFor(j,i-1,0) res |= 63-clz(t[j][res>>(j+1)*6]) << j*6;
				return res;
			}
		}
		return -1;
	}
	int qry(int x) { return t[0][x>>6] & 1ull<<(x&63) ? 1 : -1; }
} ;

块状

  • 块状链表，值域分块

值域同序列长度

// LG4278 带插入区间K小值
const int N = 7e4+5, B = 512, BN = N/B+5;
struct DS { // 值域分块
	int sum[BN],cnt[N];
	void add(int x,int y) { sum[x/B] += y, cnt[x] += y; }
};
struct Blk : Vi {
	DS ds;
	void ins(int i,int x) { emplace(begin()+i,x), ds.add(x,1); }
}; vector<Blk> bk(1); // 块状链表

Pii find(int p) { // 块状链表定位 p 位置
	Rep(i,0,sz(bk))
		if( p < sz(bk[i]) ) return {i,p};
		else p -= sz(bk[i]);
	return {sz(bk)-1,sz(bk.back())};
}

void ins(int p,int x) { // p 位置前插入 x
	int i,j; tie(i,j) = find(p);
	bk[i].ins(j,x);
	Rep(k,i+1,sz(bk)) bk[k].ds.add(x,1);
	if( sz(bk[i]) > 2*B ) {
		Vi a(bk[i].end()-B,bk[i].end());
		bk[i].erase(bk[i].end()-B,bk[i].end()),
		bk.emplace(bk.begin()+i+1,Blk()), bk[i+1].ds = bk[i].ds;
		for(int k : a) bk[i].ds.add(k,-1), bk[i+1].pb(k);
	}
}
void mdf(int p,int x) { // p 位置的值改为 x
	int i,j; tie(i,j) = find(p);
	int y = bk[i][j]; bk[i][j] = x;
	Rep(k,i,sz(bk)) bk[k].ds.add(x,1), bk[k].ds.add(y,-1);
}
int qry(int l,int r,int x) { // 查询 [l,r] 第 x 小
	static DS ds;
	int li,lj,ri,rj; tie(li,lj) = find(l), tie(ri,rj) = find(r);
	auto add=[&](int y) {
		if( li == ri ) For(i,lj,rj) ds.add(bk[li][i],y);
		else {
			Rep(i,lj,sz(bk[li])) ds.add(bk[li][i],y);
			For(i,0,rj) ds.add(bk[ri][i],y);
		}
	};
	add(1);
	for(int i = 0; ; ++i) {
		int y = ds.sum[i] + (li<ri?bk[ri-1].ds.sum[i]-bk[li].ds.sum[i]:0);
		if( x > y ) x -= y;
		else {
			i = i*B-1;
			do
				++i,
				x -= ds.cnt[i] + (li<ri?bk[ri-1].ds.cnt[i]-bk[li].ds.cnt[i]:0);
			while( x > 0 );
			add(-1);
			return i;
		}
	}
}

标签：ch,int,void,len,bk,ls,数据结构,模板
From： https://www.cnblogs.com/ft61/p/18365127

相关文章

  • 数据结构----链表
    一丶概念     链表又称单链表、链式存储结构，用于存储逻辑关系为“一对一”的数据。      和顺序表不同同，使用链表存储数据，不强制要求数据在内存中集中存储，各个元素可以分散存储在内存中。二丶特点     特点：内存不连续，通过指针进行连接 ......
  • Ruby模板引擎：构建动态视图的艺术
    标题：Ruby模板引擎：构建动态视图的艺术在RubyonRails的世界里，模板引擎是构建动态网页的基石。它们允许开发者将服务器端的逻辑嵌入到HTML中，实现数据的动态展示。本文将深入探讨Ruby中几种常用的模板引擎，包括ERB、Haml和Slim，分析它们的特色、优缺点，并指导如何在项目中做出选......
  • 二分查找(算法详解+模板+例题)
    一.二分的定义二分法（Bisectionmethod）即一分为二的方法.设[a，b]为R的闭区间.逐次二分法就是造出如下的区间序列([an，bn])：a0=a，b0=b，且对任一自然数n，[an+1，bn+1]或者等于[an，cn]，或者等于[cn，bn]，其中cn表示[an，bn]的中点。二.基本思路1.将数组排序。2.一直将数组除以二，直到找到那......
  • 数据结构与算法——BFS(广度优先搜索)
    算法介绍：广度优先搜索（Breadth-FirstSearch，简称BFS）是一种遍历或搜索树和图的算法，也称为宽度优先搜索，BFS算法从图的某个节点开始，依次对其所有相邻节点进行探索和遍历，然后再对这些相邻节点的相邻节点进行探索，直到遍历完所有的节点。BFS算法使用队列来辅助实现，将起始节点放入队列......
  • 【网络流模板题 EK增广路】luogu P2740 [USACO4.2] 草地排水Drainage Ditches)
    [P2740USACO4.2]草地排水DrainageDitches)大意:网络流模板做法:EK增广路#include<cstdio>#include<queue>#include<deque>#include<stack>#include<map>#include<cmath>#include<algorithm>#include<iostream>#include......
  • 【模板】网络流最大流
    最大流题目要求:给出n点m边srcsink然后每条边有uvcapacity求最大流题目链接P3376【模板】网络最大流EK(Edmonds–Karp)算法:\[\begin{align}&\color{Red}时间复杂度O(nm^2)\\&\color{Red}空间复杂度O(n+m)\\\end{align}\]#include<iostream>#include......
  • 数据结构中的双向链表
    1.链表的分类链表的结构非常多样，以下情况组合起来就是8种（2x2x2）链表结构：  在带头链表中，除了头结点，其他结点均存储有效的数据。头结点是占位子的，也叫做“哨兵位”。head结点就是头结点。 循环的链表尾结点不为NULL，不循环的链表尾结点为NULL单链表：不带头单向不循环链......
  • 数据结构与算法（五）栈
    一.定义：栈是限定仅在表尾进行插入或删除操作的线性表，因此，对栈来说，表尾端具有其特殊含义，称为栈顶（top），表头端称为栈底（bottom）。不含元素的空表称为空栈。栈是重要的线性结构之一，从数据结构的角度来说，栈也是线性表在理解栈的含义要注意：首先，它是一个线性表，也就是说栈元素具有线性......
  • 数据结构与算法（六）二叉树
    二叉树是一种数据结构，广泛用于计算机科学和编程中。它具有以下几个重要特征：1.基本定义：①二叉树：每个节点最多有两个子节点，分别称为左子节点和右子节点。②节点：二叉树的基本单位，包含数据以及指向其子节点的指针。③根节点：二叉树的第一个节点，没有父节点。④叶子节点：没有子节点的......
  • 【数据结构】数据结构 知识总复习
    文章目录1.复杂度计算1.1时间复杂度1.2空间复杂度1.3如何计算2.常见线性结构2.1顺序表和链表2.1.1顺序表(ArrayList)2.1.2链表(LinkedList)2.2栈和队列2.2.1什么是栈？什么是队列？关系是什么？2.2.2如何实现？数组链表原生实现？适配器？3.常见非线性结构3.......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99