带权并查集:
维护一个数组,保存一个fa[x]与x之间的关系,路径压缩时直接要记得修改关系
int find(int x) { if(fa[x]==x) { return fa[x]; } int root=find(fa[x]); w[x]=f(w[x],w[fa[x]]);//关键 fa[x]=root; return fa[x]; }
对于区间修改:
1)差分
2)懒标记
线段树:
要求:具有结合律
难点:1)思考节点中的信息,以及如何上传、下传
2)debug
![](https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)
struct segment_tree{ int l,r,lazy,dat; } t[N*4]; int a[N]; int n,m; inline void pushdown(segment_tree &u,segment_tree &l,segment_tree &r) { l.lazy+=u.lazy,r.lazy+=u.lazy; l.dat+=u.lazy*(l.r-l.l+1),r.dat+=u.lazy*(r.r-r.l+1); u.lazy=0; return ; } inline void pushdown(int u) { pushdown(t[u],t[u<<1],t[u<<1|1]); return ; } inline void pushup(segment_tree &u,segment_tree l,segment_tree r) { u.dat=l.dat+r.dat; return ; } inline void pushup(int u) { pushup(t[u],t[u<<1],t[u<<1|1]); return ; } void build(int u,int l,int r) { auto &s=t[u]; s.l=l,s.r=r; if(l==r) { s.lazy=0; s.dat=a[l]; return ; } int mid=(l+r)>>1; build(u<<1,l,mid); build(u<<1|1,mid+1,r); pushup(u); } void add(int u,int l,int r,int x) { auto &s=t[u]; if(l<=s.l && s.r<=r) { s.lazy+=x; s.dat+=x*(s.r-s.l+1); return ; } int mid=(s.l+s.r)>>1; if(s.lazy) { pushdown(u); } if(l<=mid) add(u<<1,l,r,x); if(mid<r) add(u<<1|1,l,r,x); pushup(u); return ; } int ask(int u,int l,int r) { auto &s=t[u]; if(l<=s.l && s.r<=r) { return s.dat; } int ret=0; int mid=(s.l+s.r)>>1; if(s.lazy) { pushdown(u); } if(l<=mid) ret+=ask(u<<1,l,r); if(mid+1<=r) ret+=ask(u<<1|1,l,r); return ret; }View Code
树状数组:
常见:单点修改、区间查询
可持久化数据结构:
含义:保存历史状况的数据结构扩展
要求:数据结构修改中,拓扑结构不变
方式:每次操作增加一个次版本的根,然后与上一版本连接,并新建出这次修改的节点,使得从此次的根进入可以得到此次修改后的状态
int build(int l,int r) { int p=++cnt; auto &s=t[p]; if(l>=r) { return p; } int mid=(l+r)>>1; s.lc=build(l,mid); s.rc=build(mid+1,r); return p; } int change(int v,int l,int r,int x) { int p=++cnt; auto &s=t[p]; s=t[v]; s.dat++; if(l>=r) { return p; } int mid=(l+r)>>1; if(x<=mid) s.lc=change(t[v].lc,l,mid,x); else s.rc=change(t[v].rc,mid+1,r,x); return p; }
AC自动机:
带有类似KMP的nxt数组的trie结构,可以做到多模式串匹配
void build() { int q[T],head=1,tail=0; //根和第一层的ne指向根(类似前缀函数) for(int i=0;i<26;i++) { if(to[0][i]) { q[++tail]=to[0][i];//入队第一层的结点 } } while(head<=tail) { int u=q[head++]; for(int i=0;i<26;i++) { int t=to[u][i]; if(!t) to[u][i]=to[ne[u]][i]; //为了保证查询的线性,可以类比路径压缩 else ne[t]=to[ne[u]][i],q[++tail]=t;//类比前缀函数 } }
值域思想:
维护一段值域(类似桶),内容为值域区间内数的总个数,可以快速查询很多东西(比如第k大数)
扫描线思想:
看例题
发现其实总面积是一个个横向切割后得到的矩形面积之和
具体方法:
假设数对(x1,x2,y,w) ,下边为(x1,x2,y1,1),上边为(x1,x2,y2,-1) ,按照y排序,每个矩形的高为y[i]-y[i-1],宽为扫描线上非零点个数,然后将扫描线上[x1,x2]区间加上w(值域线段树)(记得离散化)
标签:lazy,return,int,fa,build,pushdown,数据结构 From: https://www.cnblogs.com/Ga1ahad-and-Scientific-Witchery/p/17458897.html