【动态开点线段树&树链剖分】【[SDOI2014]旅行】
【动态开点线段树&树链剖分】【[SDOI2014]旅行】
题目传送门
写篇题解巩固一下动态开点线段树和树链剖分,并附上模板
一、动态开点线段树
在某些题目中我们不需要把线段树的所有节点都建立出来,而是当用到某个节点时才建立该节点,从而节省空间。
用到动态开点线段树的题,一般有几个特点:
-
用普通线段树在时间上可以通过此题,但是空间上会爆
-
通过分析题目,能够确保,线段树不可能建满,即树的大小与询问有关。例如本题,最初只有n个点,若对每种宗教建一颗大小为n的线段树,那么最初结点总数最多为nlogn,加上后面的单点修改,总结点数最多为(q+n)log n,这是完全开的下的。
几个注意事项:
- 每次单点插入最多增加logn个点,每次区间修改最多会增加2logn的点,可以用来估算线段树开的结构体大小
- 动态开点线段树最好不在结构体中记录区间的左右端点,原因很简单,之所以动态开点就是为了省空间,若再记录不必要的区间端点,就有些浪费了。
二、树剖
没啥好说的,就是两遍dfs,考点都在维护链的数据结构上,熟悉模板即可。
三、对于本题
发现很难用一颗线段树同时维护每个宗教的信息,但发现,每个宗教之间的信息互不影响,于是对每个宗教分别建一颗动态开点线段树即可。
Code
#include
using namespace std;
inline int read()
{
register int x=0,w=1;
register char ch=getchar();
while((ch<'0'||ch>'9')&&ch!='-') ch=getchar();
if(ch=='-') {w=-1;ch=getchar();}
while(ch>='0'&&ch<='9') {x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
return x*w;
}
const int N=1e5+100;
int n,q,rt[N];
int w[N],c[N],top[N],dfn[N],id[N],siz[N],hs[N],d[N],fa[N],tot;
struct node{
int ls,rs,sum,maxn;
}t[N*40];
vectorv[N];
void dfs1(int x)
{
siz[x]=1;
for(int i=0;isiz[hs[x]]) hs[x]=y;
}
}
void dfs2(int x)
{
dfn[x]=++tot;
id[tot]=x;
if(hs[x]){
top[hs[x]]=top[x];
dfs2(hs[x]);
}
for(int i=0;i>1;
if(pos<=mid){
if(!t[x].ls) t[x].ls=++tot;
change(t[x].ls,pos,val,l,mid);
}
else{
if(!t[x].rs) t[x].rs=++tot;
change(t[x].rs,pos,val,mid+1,r);
}
pushup(x);
}
void dfs(int x)
{
change(rt[c[x]],dfn[x],w[x],1,n);
for(int i=0;i=l&&R<=r){
return t[x].sum;
}
int mid=L+R>>1;
int res=0;
if(l<=mid&&t[x].ls) {
res+=querysum(t[x].ls,l,r,L,mid);
}
if(r>mid&&t[x].rs){
res+=querysum(t[x].rs,l,r,mid+1,R);
}
return res;
}
int asksum(int x,int y)
{
int root=rt[c[x]];
int res=0;
while(top[x]!=top[y])
{
if(d[top[x]]d[y]) swap(x,y);
return res+querysum(root,dfn[x],dfn[y],1,n);
}
int querymax(int x,int l,int r,int L,int R)
{
if(L>=l&&R<=r){
return t[x].maxn;
}
int mid=L+R>>1;
int res=0;
if(l<=mid&&t[x].ls) {
res=max(res,querymax(t[x].ls,l,r,L,mid));
}
if(r>mid&&t[x].rs){
res=max(res,querymax(t[x].rs,l,r,mid+1,R));
}
return res;
}
int askmax(int x,int y)
{
int root=rt[c[x]];
int res=0;
while(top[x]!=top[y])
{
if(d[top[x]]d[y]) swap(x,y);
return max(res,querymax(root,dfn[x],dfn[y],1,n));
}
int main()
{
n=read();q=read();
for(int i=1;i<=n;++i)
{
w[i]=read();
c[i]=read();
}
for(int i=1;i