2325: [ZJOI2011]道館之戰(zhàn)

Time Limit:?40 Sec??Memory Limit:?256 MB
Submit:?1153??Solved:?421
[Submit][Status][Discuss]

Description

口袋妖怪(又名神奇寶貝或寵物小精靈)紅/藍/綠寶石中的水系道館需要經(jīng)過三個冰地才能到達館主的面前，冰地中的每一個冰塊都只能經(jīng)過一次。當一個冰地上的所有冰塊都被經(jīng)過之后，到下一個冰地的樓梯才會被打開。三個冰地分別如下： 當走出第三個冰地之后，就可以與館主進行道館戰(zhàn)了。館主發(fā)現(xiàn)這個難度太小，導致經(jīng)常有挑戰(zhàn)者能通過，為了加大難度，將道館分成了n個房間，每個房間中是兩個冰塊或障礙，表示一列冰地。任意兩個房間之間均有且僅有一條路徑相連，即這n個房間構成一個樹狀結構。每個房間分成了A和B兩個區(qū)域，每一區(qū)域都是一個薄冰塊或者障礙物。每次只能移動到相鄰房間的同一類區(qū)域(即若你現(xiàn)在在這個房間的A區(qū)域，那么你只能移動到相鄰房間的A區(qū)域)或這個房間的另一區(qū)域。現(xiàn)在挑戰(zhàn)者從房間u出發(fā)，館主在房間v，那么挑戰(zhàn)者只能朝接近館主所在房間的方向過去。一開始挑戰(zhàn)者可以在房間u的任意一個冰塊區(qū)域內(nèi)。如果挑戰(zhàn)者踩過的冰塊數(shù)達到了最大值(即沒有一種方案踩過的冰塊數(shù)更多了)，那么當挑戰(zhàn)者走到最后一個冰塊上時，他會被瞬間傳送到館主面前與館主進行道館戰(zhàn)。自從館主修改規(guī)則后已經(jīng)經(jīng)過了m天，每天要么是有一個挑戰(zhàn)者來進行挑戰(zhàn)，要么就是館主將某個房間進行了修改。對于每個來的挑戰(zhàn)者，你需要計算出他若要和館主進行戰(zhàn)斗需要經(jīng)過的冰塊數(shù)。

Input

第一行包含兩個正整數(shù)n和m。第2行到第n行，每行包含兩個正整數(shù)x和y，表示一條連接房間x和房間y的邊。房間編號為1…n。接下來n行，每行包含兩個字符。第n + k行表示房間k的兩個區(qū)域，第一個字符為A區(qū)域，第二個字符為B區(qū)域。其中“.”(ASCII碼為46)表示是薄冰塊，“#”(ASCII碼為35)表示是障礙物。最后的m行，每行一個操作： l C u s：將房間u里的兩個區(qū)域修改為s。 l Q u v：詢問挑戰(zhàn)者在房間u，館主在房間v時，挑戰(zhàn)者能與館主進行挑戰(zhàn)需要踩的冰塊數(shù)。如果房間u的兩個區(qū)域都是障礙物，那么輸出0。 N≤ 30 000 M ≤ 80 000

Output

包含若干行，每行一個整數(shù)。即對于輸入中的每個詢問，依次輸出一個答案。

Sample Input

5 3
1 2
2 3
2 4
1 5
.#
..
#.
.#
..
Q 5 3
C 1 ##
Q 4 5

Sample Output

6
3

HINT

Source

Day2

Solution

樹鏈剖分+線段樹維護（類似）連通性。 ?和 堵塞的交通 維護方法類似。但是并沒有做過。

題目大意：每個節(jié)點分為ab連個塊，這些節(jié)點之間聯(lián)通呈樹形，每個節(jié)點的ab可能為障礙或者是空地，從一個節(jié)點上的a可以到這個節(jié)點的b，或者和這個節(jié)點聯(lián)通的所有a（前提是路徑上無障礙）。詢問節(jié)點x到節(jié)點y的方向上最多走多少步，支持單點修改.

這樣如果是鏈上的情況，可以等價為一個2*N的矩陣，上面一行表示所有的a，下面一行表示所有的b，等效到樹上，就是多個2*1個矩陣連成的樹。

維護方法就是，對于一個區(qū)間，維護8個量分別表示：

dis[0][0]表示從區(qū)間左端點上到右端點上，dis[0][1]表示從區(qū)間左端點下到右端點上，dis[1][0]表示從區(qū)間左端點上到右端點下，dis[1][1]表示從區(qū)間左端點下到右端點下
Dis[0][0]表示從區(qū)間左端點上最多移動數(shù)，Dis[0][1]表示從區(qū)間左端點下最多移動數(shù)，Dis[1][0]表示從區(qū)間右端點上最多移動數(shù)，Dis[1][1]表示從區(qū)間右端點下最多移動數(shù)

合并的時候就是討論一下，畫畫圖就可以得到。

有一個問題，在詢問路徑x-->y時，有一邊到LCA的路徑是從下到上的，所以在和另一邊路徑合并答案時要先反向，然后就可以了。

寫的時候要注意細節(jié)，這個在Codeing的時候由于思路清晰，寫的還是十分美觀的，就是斷斷續(xù)續(xù)自己 想+寫+調(diào) 搞了近兩個小時...（話說題意真是不清晰）

Code

#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<cmath> using namespace std; inline int read() {int x=0; char ch=getchar(); while (ch<'0' || ch>'9') ch=getchar(); while (ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar(); return x; } #define MAXN 30010 #define INF 100000000 int N,M,id[MAXN]; char mp[MAXN][3]; namespace SegmentTree {struct SgtNode{int l,r,dis[2][2],Dis[2][2]; SgtNode() { l=0,r=0; memset(dis,0,sizeof(dis)); memset(Dis,0,sizeof(Dis)); }inline bool have() {return !dis[0][0] && !dis[0][1] && !dis[1][0] && !dis[1][1] && !Dis[0][0] && !Dis[0][1] && !Dis[1][0] && !Dis[1][1];}inline void rever() { swap(dis[0][1],dis[1][0]),swap(Dis[0][0],Dis[1][0]),swap(Dis[0][1],Dis[1][1]); } inline void modify(int a,int b){dis[0][0]=a? 1:-INF; Dis[0][0]=Dis[1][0]=a; dis[1][1]=b? 1:-INF; Dis[0][1]=Dis[1][1]=b;if (a && b) Dis[0][0]=Dis[0][1]=Dis[1][0]=Dis[1][1]=dis[0][1]=dis[1][0]=2;else dis[0][1]=dis[1][0]=-INF;}//單點修改時的賦值 }tree[MAXN<<2];// dis[0][0]表示從區(qū)間左端點上到右端點上，dis[0][1]表示從區(qū)間左端點下到右端點上，dis[1][0]表示從區(qū)間左端點上到右端點下，dis[1][1]表示從區(qū)間左端點下到右端點下// Dis[0][0]表示從區(qū)間左端點上最多移動數(shù)，Dis[0][1]表示從區(qū)間左端點下最多移動數(shù)，Dis[1][0]表示從區(qū)間右端點上最多移動數(shù)，Dis[1][1]表示從區(qū)間右端點下最多移動數(shù) #define ls now<<1#define rs now<<1|1inline void update(SgtNode &rt,SgtNode lson,SgtNode rson){SgtNode tmp=rt;if (lson.have()) {rt=rson; rt.l=tmp.l; rt.r=tmp.r; return;} if (rson.have()) {rt=lson; rt.l=tmp.l; rt.r=tmp.r; return;}rt.dis[0][0]=max( max( lson.dis[0][0]+rson.dis[0][0] , lson.dis[0][1]+rson.dis[1][0] ) , -INF);rt.dis[0][1]=max( max( lson.dis[0][0]+rson.dis[0][1] , lson.dis[0][1]+rson.dis[1][1] ) , -INF);rt.dis[1][0]=max( max( lson.dis[1][0]+rson.dis[0][0] , lson.dis[1][1]+rson.dis[1][0] ) , -INF);rt.dis[1][1]=max( max( lson.dis[1][1]+rson.dis[1][1] , lson.dis[1][0]+rson.dis[0][1] ) , -INF);rt.Dis[0][0]=max( lson.Dis[0][0] , max( lson.dis[0][0]+rson.Dis[0][0] , lson.dis[0][1]+rson.Dis[0][1] ) );rt.Dis[0][1]=max( lson.Dis[0][1] , max( lson.dis[1][0]+rson.Dis[0][0] , lson.dis[1][1]+rson.Dis[0][1] ) );rt.Dis[1][0]=max( rson.Dis[1][0] , max( rson.dis[0][0]+lson.Dis[1][0] , rson.dis[1][0]+lson.Dis[1][1] ) );rt.Dis[1][1]=max( rson.Dis[1][1] , max( rson.dis[0][1]+lson.Dis[1][0] , rson.dis[1][1]+lson.Dis[1][1] ) );}inline void Update(int now) {update(tree[now],tree[ls],tree[rs]);}inline void Modify(int now,int pos,char MP[]){int l=tree[now].l,r=tree[now].r;if (l==r) {tree[now].modify(MP[1]=='.',MP[2]=='.'); return;}int mid=(l+r)>>1;if (pos<=mid) Modify(ls,pos,MP); else Modify(rs,pos,MP);Update(now);}inline SgtNode Query(int now,int L,int R){int l=tree[now].l,r=tree[now].r;if (l==L && R==r) return tree[now];int mid=(l+r)>>1; SgtNode ret;if (R<=mid) return Query(ls,L,R);else if (L>mid) return Query(rs,L,R);else return update(ret,Query(ls,L,mid),Query(rs,mid+1,R)),ret;}inline void Build(int now,int l,int r){tree[now].l=l; tree[now].r=r;if (l==r) return;int mid=(l+r)>>1;Build(ls,l,mid); Build(rs,mid+1,r);} } using namespace SegmentTree; namespace Divide {struct EdgeNode{int next,to;}edge[MAXN<<1];int head[MAXN],cnt=1;inline void AddEdge(int u,int v) {cnt++; edge[cnt].to=v; edge[cnt].next=head[u]; head[u]=cnt;}inline void InsertEdge(int u,int v) {AddEdge(u,v); AddEdge(v,u);}int deep[MAXN],fa[MAXN],size[MAXN],son[MAXN],pl[MAXN],dfn,top[MAXN];inline void DFS_1(int now,int last){size[now]=1;for (int i=head[now]; i; i=edge[i].next)if (edge[i].to!=last){fa[edge[i].to]=now;deep[edge[i].to]=deep[now]+1;DFS_1(edge[i].to,now);size[now]+=size[edge[i].to];if (size[son[now]]<size[edge[i].to]) son[now]=edge[i].to;}}inline void DFS_2(int now,int chain){pl[now]=++dfn; top[now]=chain;if (son[now]) DFS_2(son[now],chain);for (int i=head[now]; i; i=edge[i].next)if (edge[i].to!=fa[now] && edge[i].to!=son[now])DFS_2(edge[i].to,edge[i].to);}inline void Modify(int pos,char MP[]) {SegmentTree::Modify(1,pl[pos],MP);}inline void GetAns(int x,int y){SgtNode la,ra,ans; ra.l=ra.r=1; la.l=la.r=1;while (top[x]!=top[y])if (deep[top[x]]<deep[top[y]]) update(ra,Query(1,pl[top[y]],pl[y]),ra),y=fa[top[y]];else update(la,Query(1,pl[top[x]],pl[x]),la),x=fa[top[x]];if (deep[x]<deep[y]) update(ra,Query(1,pl[x],pl[y]),ra);elseupdate(la,Query(1,pl[y],pl[x]),la);la.rever(); update(ans,la,ra);printf("%d\n",max(ans.Dis[0][0],ans.Dis[0][1]));}inline void BuildTree() {for (int i=1; i<=N; i++) Modify(i,mp[i]);} } using namespace Divide; int main() { // freopen("fight.in","r",stdin); freopen("fight.out","w",stdout);N=read(),M=read();for (int x,y,i=1; i<=N-1; i++) x=read(),y=read(),InsertEdge(x,y);Divide::DFS_1(1,0); Divide::DFS_2(1,1);for (int i=1; i<=N; i++) scanf("%s",mp[i]+1);SegmentTree::Build(1,1,N); Divide::BuildTree();while (M--){char opt[2],MP[3]; scanf("%s",opt); int L,R,p;switch (opt[0]){case 'Q' : L=read(),R=read(); Divide::GetAns(L,R); break;case 'C' : p=read(); scanf("%s",MP+1); Divide::Modify(p,MP); break;}}return 0; }

轉載于:https://www.cnblogs.com/DaD3zZ-Beyonder/p/5978653.html

總結

以上是生活随笔為你收集整理的【BZOJ-2325】道馆之战 树链剖分 + 线段树的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。