【題目描述】
HYSBZ - 2243染色

【題目分析】
我一直沒有看清楚題，以為求的是路徑上出現顏色的種類，然后就寫了一個區間染色的線段樹進行維護，過樣例的時候才發現題讀錯了，人家要求的是路徑上出現的顏色段，所以顏色的種類不重要，重要的是每一段每一段。理所當然，我們應該用線段樹維護所在區間有多少段。但是左右區間上傳的時候如果邊界顏色相同（左節點的右邊界和右節點的左邊界），那么區間個數應該減一。為此，我們還必須維護每個區間左邊界和右邊界分別是什么顏色以方便查詢和上傳。因為題目是區間修改，所以我們還要用lazy標記。（用lazy標記的時候要時時記得標記下傳，就是因為單點查詢的時候忘記要標記下傳wa了一下午）
因為在樹上，所以我們不僅僅需要判斷線段樹區間合并的時候左右端點顏色是否相同，還要判斷每條鏈頂和鏈頂的父節點的顏色是否相同，如果相同答案減一。（每條鏈都在向鏈頂合并）

【AC代碼】

#include<iostream> #include<cstdio> #include<vector> #include<cmath> #include<cstring> #include<algorithm> #include<climits>using namespace std;const int MAXN=100005; //時刻注意數據范圍 vector<int>g[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 cnt=0,n,m; int num[MAXN<<2],lazy[MAXN<<2]; int lc[MAXN<<2],rc[MAXN<<2];void dfs1(int u,int f) {int i,v;siz[u]=1;son[u]=0;fa[u]=f;h[u]=h[f]+1;for(i=0;i<g[u].size();i++){v=g[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(i=0;i<g[u].size();i++){v=g[u][i];if(v!=f&&v!=son[u]) dfs2(v,u,v);} }void pushup(int k) {num[k]=num[k<<1]+num[k<<1|1];if(rc[k<<1]==lc[k<<1|1]) num[k]--; //如果左右區間的連接處顏色相同則答案減一lc[k]=lc[k<<1]; rc[k]=rc[k<<1|1]; }void build(int k,int l,int r) {if(l==r){num[k]=1;lc[k]=rc[k]=color[l];return;}int mid=(l+r)>>1;build(k<<1,l,mid);build(k<<1|1,mid+1,r);pushup(k); }void pushdown(int k) {if(lazy[k]){lazy[k<<1]=lazy[k<<1|1]=lazy[k];lc[k<<1]=lc[k<<1|1]=lazy[k];rc[k<<1]=rc[k<<1|1]=lazy[k];num[k<<1]=num[k<<1|1]=1;lazy[k]=0;} }void ColorChange(int k,int l,int r,int L,int R,int v) {if(l>=L && r<=R){num[k]=1; lazy[k]=v;lc[k]=v; rc[k]=v;return;}int mid=(l+r)>>1;pushdown(k);if(L<=mid) ColorChange(k<<1,l,mid,L,R,v);if(R>mid) ColorChange(k<<1|1,mid+1,r,L,R,v);pushup(k); }int QueryInterval(int k,int l,int r,int L,int R) {if(L<=l && r<=R){return num[k];}int mid=(l+r)/2;pushdown(k);int ret=0;if(R<=mid) return QueryInterval(k<<1,l,mid,L,R);else if(L>mid) return QueryInterval(k<<1|1,mid+1,r,L,R); //這里必須這樣寫，因為要考慮是否存在區間合并ret+=QueryInterval(k<<1,l,mid,L,R);ret+=QueryInterval(k<<1|1,mid+1,r,L,R);if(rc[k<<1]==lc[k<<1|1]) ret--;return ret; }int QueryPointColor(int k,int l,int r,int x) {if(l==r && l==x){return lc[k];}pushdown(k); //因為這里忘記了.wocint mid=(l+r)>>1;if(x<=mid) return QueryPointColor(k<<1,l,mid,x);else return QueryPointColor(k<<1|1,mid+1,r,x); }int Findnum(int u,int v) {memset(check,0,sizeof(check));int ans=0;while(top[u]!=top[v]){if(h[top[u]]<h[top[v]]) swap(u,v);ans+=QueryInterval(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--;u=fa[top[u]];}if(h[u]<h[v]) swap(u,v);ans+=QueryInterval(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);u=fa[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 i=1;i<=n;i++) scanf("%d",&val[i]);for(int i=1;i<n;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; }

總結

以上是生活随笔為你收集整理的HYSBZ - 2243染色——树链剖分+线段树建树技巧的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。