2243: [SDOI2011]染色 Time Limit: 20 Sec Memory Limit: 512 MB Description 給定一棵有n個節點的無根樹和m個操作，操作有2類： 1、將節點a到節點b路徑上所有點都染成顏色c； 2、詢問節點a到節點b路徑上的顏色段數量（連續相同顏色被認為是同一段），如“112221”由3段組成：“11”、“222”和“1”。 請你寫一個程序依次完成這m個操作。 Input 第一行包含2個整數n和m，分別表示節點數和操作數； 第二行包含n個正整數表示n個節點的初始顏色 下面 行每行包含兩個整數x和y，表示x和y之間有一條無向邊。 下面 行每行描述一個操作： “C a b c”表示這是一個染色操作，把節點a到節點b路徑上所有點（包括a和b）都染成顏色c； “Q a b”表示這是一個詢問操作，詢問節點a到節點b（包括a和b）路徑上的顏色段數量。 Output 對于每個詢問操作，輸出一行答案。 Sample Input 6 5 2 2 1 2 1 1 1 2 1 3 2 4 2 5 2 6 Q 3 5 C 2 1 1 Q 3 5 C 5 1 2 Q 3 5 Sample Output 3 1 2 HINT 數N<=10^5，操作數M<=10^5，所有的顏色C為整數且在[0, 10^9]之間。 Source 第一輪day1
/*樹鏈剖分+線段樹.讀入操作的時候要用ch[2] scanf 讀入(又被卡了).這還是shenben告訴我的%%%.以為用樹剖搞貢獻可能無法處理銜接點.然后就yy了一種類似于暴力的做法.倍增處理出lca然后跳鏈.一開始只能得70分不知道為啥(寫的很鬼畜~).原來是沒寫lca是鏈頂的情況.網上大多數人的做法是處理區間貢獻然后單點查詢判斷端點情況,一開始因為想到找鏈的時候兩個點蹦跶可能不好處理端點然后就沒這樣搞...其實我們可以先處理出段點的貢獻(還是有點暈~). 通過這題還會了手動開棧.我是找的lca然后分情況討論亂搞.這題線段樹merge什么的都還好.還有幾個需要注意的地方:build tree 標號,update &&pushtag.最重要的是讀入讀入讀入！！！*/#include<iostream>#include<cstdio>#include<algorithm>#define MAXN 100001using namespace std;struct data{int l,r,lc,rc,sum,lans,rans,bj;}tree[MAXN<<2];struct edge{int v,next;}e[MAXN*2];int n,m,cut,head[MAXN],a[MAXN];int maxsize,size[MAXN],pos[MAXN],top[MAXN],deep[MAXN],fa[MAXN][25];int read(){ int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar(); return x*f;}void add(int u,int v){ e[++cut].v=v; e[cut].next=head[u]; head[u]=cut;}void update(int k){ if(tree[tree[k].lc].rans==tree[tree[k].rc].lans) tree[k].sum=tree[tree[k].lc].sum+tree[tree[k].rc].sum-1; else tree[k].sum=tree[tree[k].lc].sum+tree[tree[k].rc].sum; tree[k].lans=tree[tree[k].lc].lans;tree[k].rans=tree[tree[k].rc].rans; return ;}void push(int k){ tree[tree[k].lc].bj=tree[tree[k].rc].bj=tree[k].bj; tree[tree[k].lc].lans=tree[tree[k].lc].rans=tree[k].bj; tree[tree[k].rc].lans=tree[tree[k].rc].rans=tree[k].bj; tree[tree[k].lc].sum=tree[tree[k].rc].sum=1; tree[k].bj=0; return ;}void build(int l,int r){ int k=++cut;tree[k].l=l,tree[k].r=r; if(l==r) return ;// 1w. int mid=(l+r)>>1; tree[k].lc=cut+1;build(l,mid); tree[k].rc=cut+1;build(mid+1,r); update(k);return ;}void change(int k,int l,int r,int z){ if(l<=tree[k].l&&tree[k].r<=r) { tree[k].sum=1; tree[k].lans=tree[k].rans=z; tree[k].bj=z; return ; } if(tree[k].bj) push(k); int mid=(tree[k].l+tree[k].r)>>1; if(l<=mid) change(tree[k].lc,l,r,z); if(r>mid) change(tree[k].rc,l,r,z); update(k);//２w. return ;}data query(int k,int l,int r){ data xx; if(l<=tree[k].l&&tree[k].r<=r) return tree[k]; if(tree[k].bj) push(k); int mid=(tree[k].l+tree[k].r)>>1; if(l>mid) return query(tree[k].rc,l,r); else if(r<=mid) return query(tree[k].lc,l,r); else { data ll=query(tree[k].lc,l,mid); data rr=query(tree[k].rc,mid+1,r); if(ll.rans==rr.lans) xx.sum=ll.sum+rr.sum-1; else xx.sum=ll.sum+rr.sum; xx.lans=ll.lans,xx.rans=rr.rans; } update(k); return xx;}void dfs1(int u){ size[u]=1; for(int i=head[u];i;i=e[i].next) { int v=e[i].v; if(!fa[v][0]) fa[v][0]=u,deep[v]=deep[u]+1,dfs1(v),size[u]+=size[v]; } return ;}void dfs2(int u,int top1){ pos[u]=++maxsize;top[u]=top1; int k=0; for(int i=head[u];i;i=e[i].next) { int v=e[i].v; if(fa[v][0]==u&&size[v]>size[k]) k=v; } if(!k) return ; dfs2(k,top1); for(int i=head[u];i;i=e[i].next) { int v=e[i].v; if(fa[v][0]==u&&v!=k) dfs2(v,v); } return ;}void slovechange(int x,int y,int z){ while(top[x]!=top[y]) { if(deep[top[x]]<deep[top[y]]) swap(x,y); change(1,pos[top[x]],pos[x],z); x=fa[top[x]][0]; } if(pos[x]>pos[y]) swap(x,y); change(1,pos[x],pos[y],z); return ;}int get_same(int u,int v){ for(int i=0;i<=20;i++) if(v&(1<<i)) u=fa[u][i]; return u;}int lca(int u,int v){ if(deep[u]<deep[v]) swap(u,v); u=get_same(u,deep[u]-deep[v]); if(u==v) return u; for(int i=20;i>=0;i--) { if(fa[u][i]!=fa[v][i]) u=fa[u][i],v=fa[v][i]; } return fa[u][0];}int get(int k,int x){ if(tree[k].l==tree[k].r) return tree[k].lans; if(tree[k].bj) push(k); int mid=(tree[k].l+tree[k].r)>>1; if(x<=mid) return get(tree[k].lc,x); else return get(tree[k].rc,x); update(k);}int slovequery(int x,int y){ /*int ans=0; while(top[x]!=top[y]) { if(deep[top[x]]<deep[top[y]]) swap(x,y); ans+=query(1,pos[top[x]],pos[x]).sum; if(get(1,pos[top[x]])==get(1,pos[fa[top[x]][0]])) ans--; x=fa[top[x]][0]; } if(pos[x]>pos[y]) swap(x,y); ans+=query(1,pos[x],pos[y]).sum; return ans;*/ data ans,ansl,ansr; int lc=lca(x,y); if(top[x]==top[y]) { if(pos[x]>pos[y]) swap(x,y); ans=query(1,pos[x],pos[y]); return ans.sum; } if(deep[lc]>deep[top[x]]||lc==top[x]) ansl=query(1,pos[lc],pos[x]); else { ansl=query(1,pos[top[x]],pos[x]);x=fa[top[x]][0]; while(deep[lc]<deep[top[x]]) { ans=query(1,pos[top[x]],pos[x]); if(ans.rans==ansl.lans) ans.sum+=ansl.sum-1; else ans.sum+=ansl.sum; ans.rans=ansl.rans; ansl=ans; x=fa[top[x]][0]; } ans=query(1,min(pos[lc],pos[x]),max(pos[lc],pos[x])); if(ans.rans==ansl.lans) ans.sum+=ansl.sum-1; else ans.sum+=ansl.sum; ans.rans=ansl.rans; ansl=ans; } if(deep[lc]>deep[top[y]]||lc==top[y]) ansr=query(1,pos[lc],pos[y]); else { ansr=query(1,pos[top[y]],pos[y]);y=fa[top[y]][0]; while(deep[lc]<deep[top[y]]) { ans=query(1,pos[top[y]],pos[y]); if(ans.rans==ansr.lans) ans.sum+=ansr.sum-1; else ans.sum+=ansr.sum; ans.rans=ansr.rans; ansr=ans; y=fa[top[y]][0]; } ans=query(1,min(pos[y],pos[lc]),max(pos[lc],pos[y])); if(ans.rans==ansr.lans) ans.sum+=ansr.sum-1; else ans.sum+=ansr.sum; ans.rans=ansr.rans; ansr=ans; } if(ansl.lans==ansr.lans) ans.sum=ansl.sum+ansr.sum-1; else ans.sum=ansl.sum+ansr.sum; return ans.sum;}void get_father(){ for(int j=1;j<=20;j++) for(int i=1;i<=n;i++) fa[i][j]=fa[fa[i][j-1]][j-1]; return ;}int main(){ freopen("paint.in","r",stdin); freopen("paint.out","w",stdout); /*int ss=64<<20; char *p=(char *)malloc(ss)+ss; __asm__("movl %0, %%esp/n"::"r"(p));*/ int x,y,z;char ch[2]; n=read(),m=read(); for(int i=1;i<=n;i++) a[i]=read(); for(int i=1;i<=n-1;i++) { x=read(),y=read(); add(x,y),add(y,x); } fa[1][0]=1;dfs1(1),dfs2(1,1); cut=0;build(1,n); for(int i=1;i<=n;i++) change(1,pos[i],pos[i],a[i]); get_father(); for(int i=1;i<=m;i++) { scanf("%s",ch);// n T.... if(ch[0]=='Q') x=read(),y=read(),新聞熱點
疑難解答
