首页 > 代码库 > 【块状树】【树链剖分】bzoj1036 [ZJOI2008]树的统计Count
【块状树】【树链剖分】bzoj1036 [ZJOI2008]树的统计Count
很早之前用树链剖分写过，但是代码太长太难写，省选现场就写错了。
1 #include<cstdio> 2 #include<algorithm> 3 #include<cstring> 4 using namespace std; 5 #define lson rt<<1,l,m 6 #define rson rt<<1|1,m+1,r 7 #define maxn 60000 8 int n,m,u,v; 9 int V[maxn],Next[maxn],First[maxn]; 10 int Val[maxn]; 11 int fa[maxn],dep[maxn],son[maxn],siz[maxn],top[maxn],Num[maxn],tot,en; 12 int maxv[maxn<<2],sumv[maxn<<2]; 13 bool vis[maxn]; 14 char s[7]; 15 inline void AddEdge(int UU,int VV) 16 { 17 V[++en]=VV; 18 Next[en]=First[UU]; 19 First[UU]=en; 20 } 21 int query_sum(int ql,int qr,int rt,int l,int r) 22 { 23 if(ql<=l&&r<=qr) 24 return sumv[rt]; 25 int m=l+r>>1,ans=0; 26 if(ql<=m) 27 ans+=query_sum(ql,qr,lson); 28 if(m<qr) 29 ans+=query_sum(ql,qr,rson); 30 return ans; 31 } 32 int query_max(int ql,int qr,int rt,int l,int r) 33 { 34 if(ql<=l&&r<=qr) 35 return maxv[rt]; 36 int m=l+r>>1,ans=-2147483647; 37 if(ql<=m) 38 ans=max(ans,query_max(ql,qr,lson)); 39 if(m<qr) 40 ans=max(ans,query_max(ql,qr,rson)); 41 return ans; 42 } 43 void update(int p,int v,int rt,int l,int r) 44 { 45 int m=l+r>>1; 46 if(l==r) 47 { 48 maxv[rt]=sumv[rt]=v; 49 return; 50 } 51 if(p<=m) 52 update(p,v,lson); 53 else 54 update(p,v,rson); 55 sumv[rt]=sumv[rt<<1]+sumv[(rt<<1)+1]; 56 maxv[rt]=max(maxv[rt<<1],maxv[(rt<<1)+1]); 57 } 58 inline void Change(int p,int v) 59 { 60 update(p,v,1,1,n); 61 } 62 inline int Query_sum(int u,int v) 63 { 64 int f1=top[u],f2=top[v],res=0; 65 while(f1!=f2) 66 { 67 if(dep[f1]<dep[f2]) 68 { 69 swap(u,v); 70 swap(f1,f2); 71 } 72 res+=query_sum(Num[f1],Num[u],1,1,n); 73 u=fa[f1]; 74 f1=top[u]; 75 } 76 if(dep[u]>dep[v]) 77 swap(u,v); 78 return res+query_sum(Num[u],Num[v],1,1,n); 79 } 80 inline int Query_max(int u,int v) 81 { 82 int f1=top[u],f2=top[v],res=-2147483647; 83 while(f1!=f2) 84 { 85 if(dep[f1]<dep[f2]) 86 { 87 swap(u,v); 88 swap(f1,f2); 89 } 90 res=max(res,query_max(Num[f1],Num[u],1,1,n)); 91 u=fa[f1]; 92 f1=top[u]; 93 } 94 if(dep[u]>dep[v]) 95 swap(u,v); 96 return max(res,query_max(Num[u],Num[v],1,1,n)); 97 } 98 void dfs1(int cur,int father,int depth) 99 {100 fa[cur]=father;101 dep[cur]=depth;102 siz[cur]=1;103 for(int i=First[cur];i;i=Next[i])104 if(!vis[V[i]])105 {106 vis[V[i]]=true;107 dfs1(V[i],cur,depth+1);108 siz[cur]+=siz[V[i]];109 if(siz[V[i]]>siz[son[cur]])110 son[cur]=V[i];111 vis[V[i]]=false;112 }113 }114 void dfs2(int cur)115 {116 if(son[cur]&&!vis[son[cur]])117 {118 vis[son[cur]]=true;119 top[son[cur]]=top[cur];120 Num[son[cur]]=++tot;121 Change(tot,Val[son[cur]]);122 dfs2(son[cur]);123 vis[son[cur]]=false;124 }125 for(int i=First[cur];i;i=Next[i])126 if(son[cur]!=V[i]&&!vis[V[i]])127 {128 vis[V[i]]=true;129 top[V[i]]=V[i];130 Num[V[i]]=++tot;131 Change(tot,Val[V[i]]);132 dfs2(V[i]);133 vis[V[i]]=false;134 }135 }136 int main()137 {138 scanf("%d",&n);139 for(int i=1;i<n;i++)140 {141 scanf("%d%d",&u,&v);142 AddEdge(u,v);143 AddEdge(v,u);144 }145 for(int i=1;i<=n;i++)146 scanf("%d",&Val[i]);147 top[1]=1;148 Num[1]=++tot;149 Change(tot,Val[1]);150 vis[1]=true;151 dfs1(1,0,1);152 dfs2(1);153 scanf("%d",&m);154 for(int i=1;i<=m;i++)155 {156 scanf("%s",s);157 if(s[1]==‘H‘)158 {159 scanf("%d%d",&u,&v);160 Change(Num[u],v);161 }162 else if(s[1]==‘M‘)163 {164 scanf("%d%d",&u,&v);165 printf("%d\n",Query_max(u,v));166 }167 else168 {169 scanf("%d%d",&u,&v);170 printf("%d\n",Query_sum(u,v));171 }172 }173 return 0;174 }
学了个块状树，好写不少，而且常数较小，比链剖慢不了多少。
在dfs时分块，只要当前块满了sqrt(n)，就分新的一块。
对每个点，维护从这个点到该块的根(top)的路径上的答案。
更新的时候，只会对 该点 在该块内的子树 造成影响。
询问时，暴力LCA。
这样更新和询问都是O(sqrt(n))的。
Orz zky。
1 #include<cstdio> 2 #include<cmath> 3 #include<algorithm> 4 using namespace std; 5 struct Graph 6 { 7 int v[60001],first[60001],next[60001],en; 8 void AddEdge(const int &a,const int &b) 9 {v[++en]=b;next[en]=first[a];first[a]=en;} 10 }; 11 Graph G[2]; 12 int fa[30001],dep[30001],top[30001],siz[30001],sz; 13 int maxv[30001],sumv[30001],w[30001]; 14 int n,x,y,q; 15 char op[10]; 16 void makeblock(int cur) 17 { 18 for(int i=G[0].first[cur];i;i=G[0].next[i]) 19 if(G[0].v[i]!=fa[cur]) 20 { 21 dep[G[0].v[i]]=dep[cur]+1; 22 fa[G[0].v[i]]=cur; 23 if(siz[top[cur]]<sz) 24 { 25 siz[top[cur]]++; 26 top[G[0].v[i]]=top[cur]; 27 G[1].AddEdge(cur,G[0].v[i]); 28 } 29 makeblock(G[0].v[i]); 30 } 31 } 32 void dfs(int cur,int Sumnow,int Maxnow) 33 { 34 maxv[cur]=Maxnow; 35 sumv[cur]=Sumnow; 36 for(int i=G[1].first[cur];i;i=G[1].next[i]) 37 dfs(G[1].v[i],Sumnow+w[G[1].v[i]],max(Maxnow,w[G[1].v[i]])); 38 } 39 inline void update(int p,int val) 40 { 41 w[p]=val; 42 if(p==top[p]) dfs(p,val,val); 43 else dfs(p,val+sumv[fa[p]],max(val,maxv[fa[p]])); 44 } 45 inline int Query_max(int u,int v) 46 { 47 int res=-2147483647; 48 while(u!=v) 49 { 50 if(top[u]==top[v]) 51 { 52 if(dep[u]<dep[v]) swap(u,v); 53 res=max(res,w[u]); 54 u=fa[u]; 55 } 56 else 57 { 58 if(dep[top[u]]<dep[top[v]]) swap(u,v); 59 res=max(res,maxv[u]); 60 u=fa[top[u]]; 61 } 62 } 63 return max(res,w[u]); 64 } 65 inline int Query_sum(int u,int v) 66 { 67 int res=0; 68 while(u!=v) 69 { 70 if(top[u]==top[v]) 71 { 72 if(dep[u]<dep[v]) 73 swap(u,v); 74 res+=w[u]; 75 u=fa[u]; 76 } 77 else 78 { 79 if(dep[top[u]]<dep[top[v]]) 80 swap(u,v); 81 res+=sumv[u]; 82 u=fa[top[u]]; 83 } 84 } 85 return res+w[u]; 86 } 87 int main() 88 { 89 scanf("%d",&n); 90 for(int i=1;i<n;i++) 91 { 92 scanf("%d%d",&x,&y); 93 G[0].AddEdge(x,y); 94 G[0].AddEdge(y,x); 95 } 96 sz=sqrt(n); 97 for(int i=1;i<=n;i++) 98 { 99 scanf("%d",&w[i]);100 top[i]=i;101 siz[i]=1;102 }103 makeblock(1);104 for(int i=1;i<=n;i++)105 if(top[i]==i) dfs(i,w[i],w[i]);106 scanf("%d",&q);107 for(int i=1;i<=q;i++)108 {109 scanf("%s%d%d",op,&x,&y);110 if(op[1]==‘M‘) printf("%d\n",Query_max(x,y));111 else if(op[1]==‘H‘) update(x,y);112 else printf("%d\n",Query_sum(x,y));113 }114 return 0;115 }
【块状树】【树链剖分】bzoj1036 [ZJOI2008]树的统计Count
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。