数据结构学习笔记
Post time: 2021-04-06 18:41:58
说在前面
省选前攒一波 \(rp\)，冲几发数据结构吧……
update 2021.4.12：SDOI2021黑了…… rp--可还行。
LCT
\(Link-Cut\ Tree\)，动态树，可以动态维护一棵树或者一个森林。主要思想是实链剖分，Splay维护森林，对于每一条链维护一些值。
几个需要注意的地方:
- 码风，尽量在所有函数里用 \(x\) 表示当前节点。
- rotate和splay不一样的地方在于，需要考虑特殊情况。一定要在保证可行的前提下再操作，并且在整个操作过程中一定要保证下标为 \(0\) 的点不会被修改！
- splay里边用的栈要手写，不要用stl，太慢了。注意边界的修改。
- 写之前先想好要求的东西能不能用LCT中的refresh维护。
最近写的一波板子：
点击查看代码
struct Link_Cut_Tree{
struct Stack{
int s[N],t;
inline void clear(){t=0;}
Stack(){clear();}
inline void push(int x){s[++t]=x;}
inline int top(){return s[t];}
inline void pop(){--t;}
inline bool empty(){return !t;}
};
int fa[N],val[N],ch[N][2];bool tag[N];
inline void refresh(int x){val[x]=a[x]^val[ch[x][0]]^val[ch[x][1]];}
inline bool isroot(int x){return ch[fa[x]][0]!=x&&ch[fa[x]][1]!=x;}
inline bool chk(int x){return ch[fa[x]][1]==x;}
inline void rotate(int x){
int f=fa[x],gf=fa[f],k=chk(x),w=ch[x][k^1];
fa[x]=gf;if(!isroot(f)) ch[gf][chk(f)]=x;
if(w) fa[w]=f;ch[f][k]=w;
fa[f]=x;ch[x][k^1]=f;
refresh(f),refresh(x);
}
inline void pushdown(int x){
if(!tag[x]) return;
tag[ch[x][0]]^=1,tag[ch[x][1]]^=1,tag[x]=0;
swap(ch[x][0],ch[x][1]);
}
inline void splay(int x){
Stack st;
int p=x;
while(!isroot(p)) st.push(p),p=fa[p];
st.push(p);
while(!st.empty()) pushdown(st.top()),st.pop();
while(!isroot(x)){
int f=fa[x],gf=fa[f];
if(!isroot(f)){
if(chk(f)==chk(x)) rotate(f);
else rotate(x);
}
rotate(x);
}
}
inline void access(int x){
for(int p=0;x;p=x,x=fa[x]) splay(x),ch[x][1]=p,refresh(x);
}
inline void makeroot(int x){
access(x);
splay(x);
tag[x]^=1;
}
inline int findroot(int x){
access(x);
splay(x);
while(ch[x][0]) x=ch[x][0];
return x;
}
inline void split(int x,int y){
makeroot(x);
access(y);
splay(y);
}
inline void link(int x,int y){
makeroot(x);
if(findroot(y)!=x) fa[x]=y;
}
inline void cut(int x,int y){
split(x,y);
if(ch[y][0]==x&&!ch[x][1]) fa[x]=ch[y][0]=0;
}
inline void modify(int x,int y){
access(x);
splay(x);
a[x]=y,refresh(x);
}
}T;
UPDATE 2021.5.13:然后LCT因为十级不考了……
虚树
名字听起来高大上，但实际上没那么难。虚树用来解决树上关键点问题。如果有 \(q\) 组询问，暴力做法是 \(O(qn)\)（或者再有一个 \(\log\)），而且所有询问实际上发挥作用的点的总数的和是 \(O(n)\) 的，那么就可以用虚树来解决。
注意建立虚树过程中，用栈来记录最右链，这条链左端（左边就是 \(dfs\) 序更小的子树）的所有关键点已经被匹配了。这样就可以通过分类讨论来 \(O(k)\) 建树。建树过程中注意会调用栈顶的下面那个元素，考虑边界的时候不要出错。
建出来虚树之后基本上就和暴力做法一样了，可能还需要多在原树上预处理一点东西即可。
板子：
点击查看代码
#include
#include
#include
using namespace std;
typedef long long ll;
inline ll rd(){
ll res=0,flag=1;char c=getchar();
while(c<'0'||c>'9'){if(c=='-') flag=-1;c=getchar();}
while(c>='0'&&c<='9') res=(res<<1)+(res<<3)+(c-'0'),c=getchar();
return res*flag;
}
void wt(ll x){
if(x>9) wt(x/10);
putchar(x%10+'0');
}
inline ll min(const ll &a,const ll &b){return amaxson) maxson=siz[v],son[u]=v;
}
}
void dfs2(int u,int topf){
top[u]=topf,id[u]=++num;
if(!son[u]) return;
dfs2(son[u],topf);
for(int i=h[u];i;i=e[i].nxt){
int v=e[i].v;
if(v!=son[u]&&v!=fa[u]) dfs2(v,v);
}
}
inline int lca(int u,int v){
while(top[u]!=top[v]){
if(dep[top[u]]1&&id[t] 区间最值 & 历史最值线段树（吉老师线段树）segmenttree beats
区间最值，就是带这样操作的数据结构题：
1 x y 表示把 \(a_x\) 变为 \(\max(\min) (a_x,y)\)。
这个东西看起来很难处理，于是我们需要重新思考最初学习线段树的时候，对于lazy-tag的理解。
lazy-tag是什么？它的意义其实是一些操作的并。如果有很多个加操作在这个区间，那么可以在这里把这些操作合并，当需要用到这个区间的子区间时，再一起下传。因为如果要把所有操作都记下来复杂度显然很高，这个lazy-tag的存在保证了复杂度。
假设这个操作是 \(\max(a_x,y)\)，然后最后要求区间 \(\min\)。那么，可以维护一个区间最小值 \(mi\)，区间内值等于这个最小值的数的个数 \(c\)，以及区间次小值 \(se\)。这样的话，每次到一个节点，假设现在要区间取 \(\max\) 的数为 \(x\)，那么考虑这个值和 \(mi,se\) 的大小关系。显然，如果 \(x\leq mi\)，那么一定不会再有任何修改和贡献；如果 \(mi
历史最值的核心在于设一个 \(preadd\) 表示每个点在上一次下传之后的加法标记最大值。利用了lazy-tag合并操作的性质，合并历史最大标记之后，在pushdown的过程中可以直接用它来统计历史最大值，总的复杂度是 \(O((n+m)\log n\)。
另外，区间最值和历史最值相结合的时候，将数分成最大值和非最大值两类分别维护加法标记和历史最大加法标记，这样的复杂度在之前已经证明是 \(O(m\log^2 n)\)。这个做法看似很暴力，但是它能够启发我们在一类统计区间问题很困难时，从值域入手，对特殊值（最值）分治，通过线段树一类数据结构的优秀性质，仅仅花费 \(1\) 到 \(2\) 个 \(\log\) 转化为只需要考虑特殊值的影响，就可以比较简单和暴力地做出来。
写代码的时候注意变量的可读性以及小细节的错误，出现问题之后先默读一遍代码看看有没有细节上很显然的问题。
模板P6242
点击查看代码
#include
#include
using namespace std;
typedef long long ll;
inline int max(const int &a,const int &b){return a>b?a:b;}
inline int min(const int &a,const int &b){return a9)wt(x/10);putchar(x%10+'0');}
const int N=5e5+13,INF=0x3f3f3f3f;
struct SegTree{int l,r,maxx,premax,se,cnt,add,preadd,addmax,preaddmax;ll sum;}t[N<<2];
int n,m;
#define ls p<<1
#define rs p<<1|1
#define mid ((t[p].l+t[p].r)>>1)
inline void refresh(int p){
t[p].sum=t[ls].sum+t[rs].sum;
t[p].premax=max(t[ls].premax,t[rs].premax);
if(t[ls].maxx>t[rs].maxx) t[p].maxx=t[ls].maxx,t[p].cnt=t[ls].cnt,t[p].se=max(t[ls].se,t[rs].maxx);
else if(t[ls].maxx==t[rs].maxx) t[p].maxx=t[ls].maxx,t[p].cnt=t[ls].cnt+t[rs].cnt,t[p].se=max(t[ls].se,t[rs].se);
else t[p].maxx=t[rs].maxx,t[p].cnt=t[rs].cnt,t[p].se=max(t[ls].maxx,t[rs].se);
}
void build(int p,int l,int r){
t[p].l=l,t[p].r=r;
if(l==r){t[p].sum=t[p].maxx=t[p].premax=rd(),t[p].se=-INF,t[p].cnt=1;return;}
build(ls,l,mid);build(rs,mid+1,r);
refresh(p);
}
inline void pushup(int p,int x,int px,int x_m,int px_m){
t[p].sum+=1ll*t[p].cnt*x_m+1ll*(t[p].r-t[p].l+1-t[p].cnt)*x;
t[p].premax=max(t[p].premax,t[p].maxx+px_m);
t[p].preadd=max(t[p].preadd,t[p].add+px);
t[p].preaddmax=max(t[p].preaddmax,t[p].addmax+px_m);
t[p].add+=x,t[p].addmax+=x_m,t[p].maxx+=x_m;
if(t[p].se!=-INF) t[p].se+=x;
}
inline void pushdown(int p){
int tmp=max(t[ls].maxx,t[rs].maxx);
if(t[ls].maxx==tmp) pushup(ls,t[p].add,t[p].preadd,t[p].addmax,t[p].preaddmax);
else pushup(ls,t[p].add,t[p].preadd,t[p].add,t[p].preadd);
if(t[rs].maxx==tmp) pushup(rs,t[p].add,t[p].preadd,t[p].addmax,t[p].preaddmax);
else pushup(rs,t[p].add,t[p].preadd,t[p].add,t[p].preadd);
t[p].add=t[p].preadd=t[p].addmax=t[p].preaddmax=0;
}
void update(int p,int l,int r,int x){
if(l<=t[p].l&&t[p].r<=r) return pushup(p,x,x,x,x);
pushdown(p);
if(l<=mid) update(ls,l,r,x);
if(r>mid) update(rs,l,r,x);
refresh(p);
}
void modify(int p,int l,int r,int x){
if(x>=t[p].maxx) return;
if(l<=t[p].l&&t[p].r<=r&&x>t[p].se) return pushup(p,0,0,x-t[p].maxx,x-t[p].maxx);
pushdown(p);
if(l<=mid) modify(ls,l,r,x);
if(r>mid) modify(rs,l,r,x);
refresh(p);
}
ll query_sum(int p,int l,int r){
if(l<=t[p].l&&t[p].r<=r) return t[p].sum;
pushdown(p);ll res=0;
if(l<=mid) res+=query_sum(ls,l,r);
if(r>mid) res+=query_sum(rs,l,r);
return res;
}
int query_max(int p,int l,int r){
if(l<=t[p].l&&t[p].r<=r) return t[p].maxx;
pushdown(p);int res=-INF;
if(l<=mid) res=max(res,query_max(ls,l,r));
if(r>mid) res=max(res,query_max(rs,l,r));
return res;
}
int query_premax(int p,int l,int r){
if(l<=t[p].l&&t[p].r<=r) return t[p].premax;
pushdown(p);int res=-INF;
if(l<=mid) res=max(res,query_premax(ls,l,r));
if(r>mid) res=max(res,query_premax(rs,l,r));
return res;
}
inline void file(){
freopen("P6242_1.in","r",stdin);
freopen("P6242.out","w",stdout);
}
int main(){
//file();
n=rd(),m=rd();
build(1,1,n);
while(m--){
int op,l,r,x;
op=rd(),l=rd(),r=rd();
switch(op){
case 1:x=rd();update(1,l,r,x);break;
case 2:x=rd();modify(1,l,r,x);break;
case 3:printf("%lld\n",query_sum(1,l,r));break;
case 4:printf("%d\n",query_max(1,l,r));break;
case 5:printf("%d\n",query_premax(1,l,r));break;
}
}
return 0;
}
李超线段树
李超树是一种用来维护线段的线段树。考虑如果说有 \(m\) 个线段加入，并且有很多次查询某个 \(x\) 坐标上的最大线段，无法用普通的线段树来做，这时候就需要李超树。李超树的核心思想在于，记录每个区间的当前“最优”线段，最后因为只有单点查询，所以直接统计线段树上这个点到根的路径上所有线段的最优值即可。
考虑现在加入一个线段 \(u\)，当前节点的最优线段编号为 \(v\)，那么分类讨论：
首先对斜率大小进行讨论：
若 \(u.k=v.k\)，那么只需要比较两条线段在 \(mid\) 处的值大小，大的那条线段在任何位置都一定更优，可以直接退出。
若 \(u.k>v.k\)，比较两条线段在 \(mid\) 处的取值 \(val(u,mid)\) 和 \(val(v,mid)\)：
- \(val(u,mid)>val(v,mid)\)，\(u\) 在右边（即\((mid+1,r)\)）一定更优，\(v\) 在左边可能更优；
- \(val(u,mid)
若 \(u.k
- \(val(u,mid)>val(v,mid)\)，\(u\) 在左边一定更优，\(v\) 在右边可能更优；
- \(val(u,mid)
所有 \(val(u,mid)=val(v,mid)\) 的情况都可以被归到两种情况中的任何一种。
现在已经讨论完了所有情况，考虑如何实现 \(update\) 一条直线。可以发现，如果在当前节点表示的区间，最优线段是 \(u\)，那么这个线段就不需要再下传了。只有当它被一条更优的线段取代的时候，通过上边的分析，如果说它在下面的某个区间还可能更优的话，才会被下传。所以总共的修改复杂度为 \(O(\log^2 n)\)，询问复杂度为 \(O(\log n)\)。
模板P4097
点击查看代码
#include
#include
#include
using namespace std;
const int N=40000+13,M=1e5+13;
const double eps=1e-10;
struct Segment{double k,b;}a[M];
struct Node{
int id;double y;
bool operator<(const Node &a)const{
if(fabs(y-a.y)a.id;
return y>1)
void build(int p,int l,int r){
t[p].l=l,t[p].r=r;
if(l==r) return;
build(ls,l,mid);build(rs,mid+1,r);
}
void update(int p,int l,int r,int id){
if(l<=t[p].l&&t[p].r<=r){
if(!t[p].id){t[p].id=id;return;}
if(t[p].l==t[p].r){
if(val(id,t[p].l)>val(t[p].id,t[p].l)) t[p].id=id;
return;
}
if(fabs(a[id].k-a[t[p].id].k)val(t[p].id,mid)) t[p].id=id;
}
else if(a[id].k>a[t[p].id].k){
if(val(id,mid)>val(t[p].id,mid)){
update(ls,l,r,t[p].id);
t[p].id=id;
}
else update(rs,l,r,id);
}
else{
if(val(id,mid)>val(t[p].id,mid)){
update(rs,l,r,t[p].id);
t[p].id=id;
}
else update(ls,l,r,id);
}
return;
}
if(l<=mid) update(ls,l,r,id);
if(r>mid) update(rs,l,r,id);
}
Node query(int p,int x){
Node res=(Node){t[p].id,val(t[p].id,x)};
if(t[p].l==t[p].r) return res;
return max(res,x<=mid?query(ls,x):query(rs,x));
}
int main(){
//freopen("P4097_1.in.txt","r",stdin);
//freopen("P4097.out","w",stdout);
build(1,1,n);
scanf("%d",&m);int lastans=0;
while(m--){
int op,x0,y0,x1,y1,x;
scanf("%d",&op);
if(op){
scanf("%d%d%d%d",&x0,&y0,&x1,&y1);
x0=(x0+lastans-1)%n+1,x1=(x1+lastans-1)%n+1;
y0=(y0+lastans-1)%lim+1,y1=(y1+lastans-1)%lim+1;
if(x0>x1) swap(x0,x1),swap(y0,y1);
int id=add(x0,y0,x1,y1);
update(1,x0,x1,id);
}
else{
scanf("%d",&x);x=(x+lastans-1)%n+1;
Node ans=query(1,x);
printf("%d\n",(lastans=ans.id));
}
}
return 0;
}
线段树分治
线段树分治是一个解决在线算法不够优秀的离线做法。首先在时间轴上建立线段树，然后把所有修改放到线段树的 \(O(\log n)\) 个区间内，最后dfs线段树一遍求出叶子节点的答案。注意这里的修改操作必须支持可撤销，比如并查集只能按秩合并，并且要用栈来支持可撤销。
板子题大概是说，需要判断一个图是二分图当且仅当其没有奇环。奇环的求法就是扩展域并查集。
模板P5787
点击查看代码
#include
#include
#include
#include
using namespace std;
inline int rd(){
int res=0;char c=getchar();
for(;!isdigit(c);c=getchar());
for(;isdigit(c);c=getchar())res=(res<<1)+(res<<3)+(c-'0');
return res;
}
const int N=2e5+13;
int n,m,k;bool ans[N];
struct edge{int u,v;}E[N];
struct SegTree{int l,r;vectore;}t[N<<2];
#define ls p<<1
#define rs p<<1|1
#define mid ((t[p].l+t[p].r)>>1)
void build(int p,int l,int r){
t[p].l=l,t[p].r=r;
if(l==r) return;
build(ls,l,mid),build(rs,mid+1,r);
}
void update(int p,int l,int r,int x){
if(l<=t[p].l&&t[p].r<=r) return t[p].e.push_back(x);
if(l<=mid) update(ls,l,r,x);
if(r>mid) update(rs,l,r,x);
}
struct Node{int x,y,k;};
stack s;
int fa[N],dep[N];
int find(int x){return fa[x]==x?x:find(fa[x]);}
inline void merge(int u,int v){
int x=find(u),y=find(v);
if(x==y) return;
if(dep[x]>dep[y]) swap(x,y);
fa[x]=y,dep[y]+=(dep[x]==dep[y]);
s.push((Node){x,y,dep[x]==dep[y]});
}
inline bool check(int u,int v){return find(u)==find(v);}
void dfs(int p){
int lim=t[p].e.size(),tmp=s.size();bool flag=1;
for(int i=0;itmp){
fa[s.top().x]=s.top().x,dep[s.top().y]-=s.top().k;
s.pop();--lim;
}
}
int main(){
n=rd(),m=rd(),k=rd();
build(1,1,k);
for(int i=1;i<=m;++i){
E[i].u=rd(),E[i].v=rd();
int l=rd(),r=rd();
if(l 笛卡尔树
笛卡尔树是一种二叉搜索树，每个点有两个权值 \((x_i,y_i)\)，满足两个条件：
- 所有的 \(x_i\) 形成一棵二叉搜索树。
- 所有的 \(y_i\) 形成一个小根堆。
一般的建立是先使 \(x_i\) 单调增，这样每次插入的点如果是原来的点的孩子，那一定是右儿子；如果原来的点是这个点的孩子，那么一定是左儿子。然后就有一个 \(O(n)\) 建立笛卡尔树的方法：
拿单调栈存储当前树的最右链（一直走右儿子的链），那么每次一个点进来，一定是在这条链上找到深度最大的 \(y
模板P5854
点击查看代码
#include
#include
#define rint register int
using namespace std;
inline int rd(){
int res=0;char c=getchar();
for(;!isdigit(c);c=getchar());
for(;isdigit(c);c=getchar())res=(res<<1)+(res<<3)+(c-'0');
return res;
}
const int N=1e7+13;
int n,a[N],s[N],top,L[N],R[N];
int main(){
n=rd();
for(rint i=1;i<=n;++i){
a[i]=rd();rint pos=top;
while(pos&&a[s[pos]]>a[i]) --pos;
if(pos) R[s[pos]]=i;
if(pos 点分治
点分治可以解决一类树上的问题。板子题说的是问一棵边有权的树上有没有距离为 \(k\) 的点对。
做法有两种：第一种是，枚举这个距离的中间点，直接在子树中匹配。具体做法是把子树中所有的 \(d\) 都加到一个数据结构里，后面的每个 \(d\) 进来的时候，在数据结构里查找有没有值为 \(k-d\) 并且不在同一个子树内的。如果有那么这个询问的答案就可以。这个做法使用桶可以做到 \(O(nm\log n)\)。
但是，如果不能使用桶（数据范围很大），可能就需要使用平衡树维护。第二种做法是一个不错的解决方式：把子树内所有点都放到一个数组里，按照 \(d\) 从小到大排序，然后定义两个指针 \(l,r\) 分别从头和尾来扫。注意到因为 \(l\) 单调递增，那么 \(r\) 只会单调不减，所以扫一遍的复杂度是 \(O(n)\) 的。
等等，是不是有什么问题？树是一条链的话，复杂度是不是假了？
怎么解决这个问题呢？考虑每次进入一个子树的时候，先找到子树的重心，这样每一次往下递归都会减少至少 \(\frac12\)，所以总共需要上面那样扫的次数是 \(O(\log n)\) 的，算上排序，总共的复杂度是 \(O(n\log^2 n+nm\log n)\)。
点击查看代码
#include
#include
#include
using namespace std;
inline int max(const int &a,const int &b){return a>b?a:b;}
const int N=1e4+13;
struct Edge{int v,w,nxt;}e[N<<1];
int n,m,q[N],tot,cnt,h[N],rt,siz[N],maxson[N],a[N],b[N],d[N];
bool vis[N],ans[N];
inline bool cmp(const int &x,const int &y){return d[x]q[i]) --r;
else if(d[a[l]]+d[a[r]]