【BZOJ-2325】道馆之战 树链剖分 + 线段树

2325: [ZJOI2011]道馆之战

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

Description

口袋妖怪(又名神奇宝贝或宠物小精灵)红/蓝/绿宝石中的水系道馆需要经过三个冰地才能到达馆主的面前，冰地中的每一个冰块都只能经过一次。当一个冰地上的所有冰块都被经过之后，到下一个冰地的楼梯才会被打开。三个冰地分别如下： 当走出第三个冰地之后，就可以与馆主进行道馆战了。馆主发现这个难度太小，导致经常有挑战者能通过，为了加大难度，将道馆分成了n个房间，每个房间中是两个冰块或障碍，表示一列冰地。任意两个房间之间均有且仅有一条路径相连，即这n个房间构成一个树状结构。每个房间分成了A和B两个区域，每一区域都是一个薄冰块或者障碍物。每次只能移动到相邻房间的同一类区域(即若你现在在这个房间的A区域，那么你只能移动到相邻房间的A区域)或这个房间的另一区域。现在挑战者从房间u出发，馆主在房间v，那么挑战者只能朝接近馆主所在房间的方向过去。一开始挑战者可以在房间u的任意一个冰块区域内。如果挑战者踩过的冰块数达到了最大值(即没有一种方案踩过的冰块数更多了)，那么当挑战者走到最后一个冰块上时，他会被瞬间传送到馆主面前与馆主进行道馆战。自从馆主修改规则后已经经过了m天，每天要么是有一个挑战者来进行挑战，要么就是馆主将某个房间进行了修改。对于每个来的挑战者，你需要计算出他若要和馆主进行战斗需要经过的冰块数。

Input

第一行包含两个正整数n和m。第2行到第n行，每行包含两个正整数x和y，表示一条连接房间x和房间y的边。房间编号为1…n。接下来n行，每行包含两个字符。第n + k行表示房间k的两个区域，第一个字符为A区域，第二个字符为B区域。其中“.”(ASCII码为46)表示是薄冰块，“#”(ASCII码为35)表示是障碍物。最后的m行，每行一个操作： l C u s：将房间u里的两个区域修改为s。 l Q u v：询问挑战者在房间u，馆主在房间v时，挑战者能与馆主进行挑战需要踩的冰块数。如果房间u的两个区域都是障碍物，那么输出0。 N≤ 30 000 M ≤ 80 000

Output

包含若干行，每行一个整数。即对于输入中的每个询问，依次输出一个答案。

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

树链剖分+线段树维护（类似）连通性。  和 堵塞的交通 维护方法类似。但是并没有做过。

题目大意：每个节点分为ab连个块，这些节点之间联通呈树形，每个节点的ab可能为障碍或者是空地，从一个节点上的a可以到这个节点的b，或者和这个节点联通的所有a（前提是路径上无障碍）。询问节点x到节点y的方向上最多走多少步，支持单点修改.

这样如果是链上的情况，可以等价为一个2*N的矩阵，上面一行表示所有的a，下面一行表示所有的b，等效到树上，就是多个2*1个矩阵连成的树。

维护方法就是，对于一个区间，维护8个量分别表示：

dis[0][0]表示从区间左端点上到右端点上，dis[0][1]表示从区间左端点下到右端点上，dis[1][0]表示从区间左端点上到右端点下，dis[1][1]表示从区间左端点下到右端点下
Dis[0][0]表示从区间左端点上最多移动数，Dis[0][1]表示从区间左端点下最多移动数，Dis[1][0]表示从区间右端点上最多移动数，Dis[1][1]表示从区间右端点下最多移动数

合并的时候就是讨论一下，画画图就可以得到。

有一个问题，在询问路径x-->y时，有一边到LCA的路径是从下到上的，所以在和另一边路径合并答案时要先反向，然后就可以了。

写的时候要注意细节，这个在Codeing的时候由于思路清晰，写的还是十分美观的，就是断断续续自己 想+写+调 搞了近两个小时...（话说题意真是不清晰）

Code

#include
#include
#include
#include
#include
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]表示从区间左端点上到右端点上，dis[0][1]表示从区间左端点下到右端点上，dis[1][0]表示从区间左端点上到右端点下，dis[1][1]表示从区间左端点下到右端点下// Dis[0][0]表示从区间左端点上最多移动数，Dis[0][1]表示从区间左端点下最多移动数，Dis[1][0]表示从区间右端点上最多移动数，Dis[1][1]表示从区间右端点下最多移动数 #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]]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

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！