上海网站建设与设计公司,石家庄哪里有网站建设,甘肃省建设厅执业资格注册网站,为什么要用模板建站【题目描述】 HYSBZ - 2243染色 【题目分析】 我一直没有看清楚题#xff0c;以为求的是路径上出现颜色的种类#xff0c;然后就写了一个区间染色的线段树进行维护#xff0c;过样例的时候才发现题读错了#xff0c;人家要求的是路径上出现的颜色段#xff0c;所以颜色的…【题目描述】 HYSBZ - 2243染色 【题目分析】 我一直没有看清楚题以为求的是路径上出现颜色的种类然后就写了一个区间染色的线段树进行维护过样例的时候才发现题读错了人家要求的是路径上出现的颜色段所以颜色的种类不重要重要的是每一段每一段。理所当然我们应该用线段树维护所在区间有多少段。但是左右区间上传的时候如果边界颜色相同左节点的右边界和右节点的左边界那么区间个数应该减一。为此我们还必须维护每个区间左边界和右边界分别是什么颜色以方便查询和上传。因为题目是区间修改所以我们还要用lazy标记。用lazy标记的时候要时时记得标记下传就是因为单点查询的时候忘记要标记下传wa了一下午 因为在树上所以我们不仅仅需要判断线段树区间合并的时候左右端点颜色是否相同还要判断每条链顶和链顶的父节点的颜色是否相同如果相同答案减一。每条链都在向链顶合并
【AC代码】
#includeiostream
#includecstdio
#includevector
#includecmath
#includecstring
#includealgorithm
#includeclimitsusing namespace std;const int MAXN100005; //时刻注意数据范围
vectorintg[MAXN];
int fa[MAXN],A[MAXN],val[MAXN],color[MAXN],pos[MAXN];
bool check[MAXN];
int siz[MAXN],son[MAXN],h[MAXN],top[MAXN];
int cnt0,n,m;
int num[MAXN2],lazy[MAXN2];
int lc[MAXN2],rc[MAXN2];void dfs1(int u,int f)
{int i,v;siz[u]1;son[u]0;fa[u]f;h[u]h[f]1;for(i0;ig[u].size();i){vg[u][i];if(v!f){dfs1(v,u);siz[u]siz[v];if(siz[son[u]]siz[v]) son[u]v;}}
}
void dfs2(int u,int f,int k)
{int i,v;top[u]k;pos[u]cnt;color[cnt]val[u];if(son[u]) dfs2(son[u],u,k);for(i0;ig[u].size();i){vg[u][i];if(v!fv!son[u]) dfs2(v,u,v);}
}void pushup(int k)
{num[k]num[k1]num[k1|1];if(rc[k1]lc[k1|1]) num[k]--; //如果左右区间的连接处颜色相同则答案减一lc[k]lc[k1]; rc[k]rc[k1|1];
}void build(int k,int l,int r)
{if(lr){num[k]1;lc[k]rc[k]color[l];return;}int mid(lr)1;build(k1,l,mid);build(k1|1,mid1,r);pushup(k);
}void pushdown(int k)
{if(lazy[k]){lazy[k1]lazy[k1|1]lazy[k];lc[k1]lc[k1|1]lazy[k];rc[k1]rc[k1|1]lazy[k];num[k1]num[k1|1]1;lazy[k]0;}
}void ColorChange(int k,int l,int r,int L,int R,int v)
{if(lL rR){num[k]1; lazy[k]v;lc[k]v; rc[k]v;return;}int mid(lr)1;pushdown(k);if(Lmid) ColorChange(k1,l,mid,L,R,v);if(Rmid) ColorChange(k1|1,mid1,r,L,R,v);pushup(k);
}int QueryInterval(int k,int l,int r,int L,int R)
{if(Ll rR){return num[k];}int mid(lr)/2;pushdown(k);int ret0;if(Rmid) return QueryInterval(k1,l,mid,L,R);else if(Lmid) return QueryInterval(k1|1,mid1,r,L,R); //这里必须这样写因为要考虑是否存在区间合并retQueryInterval(k1,l,mid,L,R);retQueryInterval(k1|1,mid1,r,L,R);if(rc[k1]lc[k1|1]) ret--;return ret;
}int QueryPointColor(int k,int l,int r,int x)
{if(lr lx){return lc[k];}pushdown(k); //因为这里忘记了.wocint mid(lr)1;if(xmid) return QueryPointColor(k1,l,mid,x);else return QueryPointColor(k1|1,mid1,r,x);
}int Findnum(int u,int v)
{memset(check,0,sizeof(check));int ans0;while(top[u]!top[v]){if(h[top[u]]h[top[v]]) swap(u,v);ansQueryInterval(1,1,n,pos[top[u]],pos[u]);//printf(ans%d\n,ans);//printf(QueryPointColor(1,1,n,pos[%d])%d\nQueryPointColor(1,1,n,pos[%d])%d\n,top[u],QueryPointColor(1,1,n,pos[top[u]]),fa[top[u]],QueryPointColor(1,1,n,pos[fa[top[u]]]));if(QueryPointColor(1,1,n,pos[top[u]]) QueryPointColor(1,1,n,pos[fa[top[u]]])) //考虑链与链的合并ans--;ufa[top[u]];}if(h[u]h[v]) swap(u,v);ansQueryInterval(1,1,n,pos[v],pos[u]);//printf(ans%d\n,ans);return ans;
}void update(int u,int v,int w)
{while(top[u]!top[v]){if(h[top[u]]h[top[v]]) swap(u,v);ColorChange(1,1,n,pos[top[u]],pos[u],w);ufa[top[u]];}if(h[u]h[v]) swap(u,v);ColorChange(1,1,n,pos[v],pos[u],w);
}int main()
{int a,b,c;char s[10];scanf(%d%d,n,m);for(int i1;in;i) scanf(%d,val[i]);for(int i1;in;i){scanf(%d%d,a,b);g[a].push_back(b);g[b].push_back(a);}dfs1(1,0);dfs2(1,0,1);build(1,1,n);while(m--){scanf(%s,s);if(s[0]C){scanf(%d%d%d,a,b,c);update(a,b,c);}else if(s[0]Q) {scanf(%d%d,a,b);printf(%d\n,Findnum(a,b));}}return 0;
}
