本文主要是介绍bzoj3531（树链剖分+动态开点线段树），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
每一个颜色建一个线段树
神方法，用主席树的计算方法，因为一个点在线段树中只会产生log个点，所以总的点数是在n log n的级别内的
所以均摊下来不会MLE
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<queue>
#include<cmath>
using namespace std;
const int N=100005;int n,C,Q;
int w[N],c[N];int rt[N],tt;
struct aa
{int lc,rc,mx,sum;
}a[N*80];
//
int pre[N*2],to[N*2],tot,head[N];
void addedge(int u,int v) {to[++tot]=v;pre[tot]=head[u];head[u]=tot;}
//
int id[N],fa[N],dep[N],size[N],son[N],top[N],cnt;void dfs1(int u,int fat,int depth)
{dep[u]=depth;fa[u]=fat;size[u]=1;int mx=0,v;for (int i=head[u];i;i=pre[i])if ((v=to[i])!=fat){dfs1(v,u,depth+1);if (size[v]>mx) mx=size[v],son[u]=v;size[u]+=size[v]; }
}
void dfs2(int u,int anc)
{id[u]=++cnt,top[u]=anc;if (son[u]) dfs2(son[u],anc);int v;for (int i=head[u];i;i=pre[i])if ((v=to[i])!=fa[u]&&v!=son[u]) dfs2(v,v);
}
//
void up(int u)
{int l=a[u].lc,r=a[u].rc;a[u].mx=max(a[l].mx,a[r].mx);a[u].sum=a[l].sum+a[r].sum;
}
void updata(int &u,int l,int r,int pos,int w)
{if (u==0) u=++tt;if (l==r){a[u].mx=a[u].sum=w;return ;}int mid=(l+r)>>1;if (pos<=mid) updata(a[u].lc,l,mid,pos,w);else updata(a[u].rc,mid+1,r,pos,w);up(u);
}int q_sum(int u,int l,int r,int ql,int qr)
{if (u==0) return 0;if (l==ql&&r==qr) return a[u].sum;int mid=(l+r)>>1;if (qr<=mid) return q_sum(a[u].lc,l,mid,ql,qr);if (mid<ql) return q_sum(a[u].rc,mid+1,r,ql,qr);return q_sum(a[u].lc,l,mid,ql,mid)+q_sum(a[u].rc,mid+1,r,mid+1,qr);
}
int query_sum(int col,int x,int y)
{int ans=0;while (top[x]!=top[y]){if (dep[top[x]]<dep[top[y]]) swap(x,y);ans+=q_sum(rt[col],1,n,id[top[x]],id[x]);x=fa[top[x]];}if (dep[x]>dep[y]) swap(x,y);ans+=q_sum(rt[col],1,n,id[x],id[y]);return ans;
}int q_mx(int u,int l,int r,int ql,int qr)
{if (u==0) return 0;if (l==ql&&r==qr) return a[u].mx;int mid=(l+r)>>1;if (qr<=mid) return q_mx(a[u].lc,l,mid,ql,qr);if (mid<ql) return q_mx(a[u].rc,mid+1,r,ql,qr); return max(q_mx(a[u].lc,l,mid,ql,mid),q_mx(a[u].rc,mid+1,r,mid+1,qr));
}int query_mx(int col,int x,int y)
{int ans=0;while (top[x]!=top[y]){if (dep[top[x]]<dep[top[y]]) swap(x,y);ans=max(ans,q_mx(rt[col],1,n,id[top[x]],id[x]));x=fa[top[x]];}if (dep[x]>dep[y]) swap(x,y);ans=max(ans,q_mx(rt[col],1,n,id[x],id[y]));return ans;
}int main()
{scanf("%d%d",&n,&Q);for (int i=1;i<=n;i++) scanf("%d%d",&w[i],&c[i]);int x,y;for (int i=1;i<n;i++){scanf("%d%d",&x,&y);addedge(x,y);addedge(y,x);}dfs1(1,0,1);dfs2(1,1);for (int i=1;i<=n;i++) updata(rt[c[i]],1,n,id[i],w[i]);char ch[4];while (Q--){scanf("%s%d%d",ch,&x,&y);switch(ch[1]){case 'C':updata(rt[c[x]],1,n,id[x],0);c[x]=y;updata(rt[c[x]],1,n,id[x],w[x]);break;case 'W':w[x]=y;updata(rt[c[x]],1,n,id[x],w[x]);break;case 'S':printf("%d\n",query_sum(c[x],x,y));break;case 'M':printf("%d\n",query_mx(c[x],x,y));break;}}return 0;
}
这篇关于bzoj3531（树链剖分+动态开点线段树）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
