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
1 2
2 3
2 4
1 5
.#
..
#.
.#
..
Q 5 3
C 1 ##
Q 4 5
Sample Output
6
3
3
HINT
Source
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<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
inline int read()
{
int x=; char ch=getchar();
while (ch<'' || ch>'') ch=getchar();
while (ch>='' && ch<='') x=x*+ch-'',ch=getchar();
return x;
}
#define MAXN 30010
#define INF 100000000
int N,M,id[MAXN]; char mp[MAXN][];
namespace SegmentTree
{
struct SgtNode
{
int l,r,dis[][],Dis[][];
SgtNode() { l=,r=; memset(dis,,sizeof(dis)); memset(Dis,,sizeof(Dis)); }
inline bool have() {return !dis[][] && !dis[][] && !dis[][] && !dis[][] && !Dis[][] && !Dis[][] && !Dis[][] && !Dis[][];}
inline void rever() { swap(dis[][],dis[][]),swap(Dis[][],Dis[][]),swap(Dis[][],Dis[][]); }
inline void modify(int a,int b)
{
dis[][]=a? :-INF; Dis[][]=Dis[][]=a;
dis[][]=b? :-INF; Dis[][]=Dis[][]=b;
if (a && b) Dis[][]=Dis[][]=Dis[][]=Dis[][]=dis[][]=dis[][]=;
else dis[][]=dis[][]=-INF;
}//单点修改时的赋值
}tree[MAXN<<];
// 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|1
inline 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[][]=max( max( lson.dis[][]+rson.dis[][] , lson.dis[][]+rson.dis[][] ) , -INF);
rt.dis[][]=max( max( lson.dis[][]+rson.dis[][] , lson.dis[][]+rson.dis[][] ) , -INF);
rt.dis[][]=max( max( lson.dis[][]+rson.dis[][] , lson.dis[][]+rson.dis[][] ) , -INF);
rt.dis[][]=max( max( lson.dis[][]+rson.dis[][] , lson.dis[][]+rson.dis[][] ) , -INF);
rt.Dis[][]=max( lson.Dis[][] , max( lson.dis[][]+rson.Dis[][] , lson.dis[][]+rson.Dis[][] ) );
rt.Dis[][]=max( lson.Dis[][] , max( lson.dis[][]+rson.Dis[][] , lson.dis[][]+rson.Dis[][] ) );
rt.Dis[][]=max( rson.Dis[][] , max( rson.dis[][]+lson.Dis[][] , rson.dis[][]+lson.Dis[][] ) );
rt.Dis[][]=max( rson.Dis[][] , max( rson.dis[][]+lson.Dis[][] , rson.dis[][]+lson.Dis[][] ) );
}
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[]=='.',MP[]=='.'); return;}
int mid=(l+r)>>;
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)>>; 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+,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)>>;
Build(ls,l,mid); Build(rs,mid+,r);
}
}
using namespace SegmentTree;
namespace Divide
{
struct EdgeNode{int next,to;}edge[MAXN<<];
int head[MAXN],cnt=;
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]=;
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]+;
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(,pl[pos],MP);}
inline void GetAns(int x,int y)
{
SgtNode la,ra,ans; ra.l=ra.r=; la.l=la.r=;
while (top[x]!=top[y])
if (deep[top[x]]<deep[top[y]])
update(ra,Query(,pl[top[y]],pl[y]),ra),y=fa[top[y]];
else
update(la,Query(,pl[top[x]],pl[x]),la),x=fa[top[x]];
if (deep[x]<deep[y])
update(ra,Query(,pl[x],pl[y]),ra);
else
update(la,Query(,pl[y],pl[x]),la);
la.rever(); update(ans,la,ra);
printf("%d\n",max(ans.Dis[][],ans.Dis[][]));
}
inline void BuildTree() {for (int i=; 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=; i<=N-; i++) x=read(),y=read(),InsertEdge(x,y);
Divide::DFS_1(,); Divide::DFS_2(,);
for (int i=; i<=N; i++) scanf("%s",mp[i]+);
SegmentTree::Build(,,N); Divide::BuildTree();
while (M--)
{
char opt[],MP[]; scanf("%s",opt); int L,R,p;
switch (opt[])
{
case 'Q' : L=read(),R=read(); Divide::GetAns(L,R); break;
case 'C' : p=read(); scanf("%s",MP+); Divide::Modify(p,MP); break;
}
}
return ;
}