lyyyyyy

模板

DAG图(1) DP(15) 图论(4) 并查集(2) 搜索(3) 数学(8) 最小生成树(2) 未归档(22)

/ 注册

全部文章 / 模板（共18篇）

树剖top数组

好像很少有关于top数组性质的博客。 for(int i=top[x];fa[i];i=top[fa[i]]) 可以遍历所有子树中含有x节点的重链链头节点（或叶子节点），由于重链不超过log(n)个,所以这个循环复杂度是O(logN)的。设i是重链链头节点，f是i的父节点，则i是f的轻儿子。所以，如...

2019-11-22

0 698

平面最近点对 cdq分治

cdq分治可以很好地处理平面点对间具有某种性质的值或数量，最近点对也不例外。参考OI Wiki 先对x排序，cdq返回点集内部最近点对的距离记为mindis。考虑如何合并左右区间，对于处于点集A的点a和B的点b，显然 ∣ ...

2019-11-15

0 584

cdq分治（模板）

可求解多维偏序问题三维偏序（陌上花开）有 nn 个元素，第 ii 个元素有 a i ...

2019-11-11

0 466

快读

快读 char buf[1<<20],*P1=buf,*P2=buf; #define gc() (P1==P2&&(P2=(P1=buf)+fread(buf,1,1<<20,stdin),P1==P2)?EOF:*P1++) #define gc() g...

2019-11-03

0 464

主席树

静态主席树 #include<bits/stdc++.h> using namespace std; #define mid ((l+r)>>1) const int MAXN=10; int n,m,a[MAXN],b[MAXN],N; //a为原数组，b为离散后的数组，...

2019-11-03

0 345

splay树

伸展树 #include<bits/stdc++.h> using namespace std; template<class T> inline bool read(T &x){ x=0;register char c=getchar();register...

2019-11-03

0 667

树链剖分（边）

树链剖分（边）将边权下放至两端点中深度大的点中，当做点权维护。 #include<iostream> #include<algorithm> using namespace std; #define gc getchar template<typename T&g...

2019-11-03

0 437

树剖版lca

树剖版lca 树剖自带lca #include<bits/stdc++.h> using namespace std; template<class T>inline bool read(T &x){ x=0;register char c=getchar...

2019-11-03

0 401

树链剖分

树链剖分（点）解决：将两个节点之间的简单路径上的点的权值加上v 求两个节点之间的简单路径上的点的权值之和以某一节点为根节点的子树内所有的点的权值加上v 求某一节点为根节点的子树内所有的点的权值之和思想：将数划分成若干链，用线段树或者树状数组对这些链进行操作重...

2019-11-03

0 454

kruskal重构树

解决图中：任意两节点（可以不连通）找到x<->y路径中边权的最小的最大值，反之亦然（也可以用树剖写）给定起点，经过的路径边权有某限制下的（如小于等于某值）点权第k小（大），需要主席树。对于1：看着像二分。。对原图边权排序，生成树是直接并查集merge x，y两...

2019-11-01

0 601