「BZOJ2325」[ZJOI2011] 道馆之战
Description
口袋妖怪(又名神奇宝贝或宠物小精灵)红/蓝/绿宝石中的水系道馆需要经过三个冰地才能到达馆主的面前，冰地中的每一个冰块都只能经过一次。当一个冰地上的所有冰块都被经过之后，到下一个冰地的楼梯才会被打开。
三个冰地分别如下：
.jpg)
当走出第三个冰地之后，就可以与馆主进行道馆战了。
馆主发现这个难度太小，导致经常有挑战者能通过，为了加大难度，将道馆分成了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。
Output
包含若干行，每行一个整数。即对于输入中的每个询问，依次输出一个答案。
Sample Input
1 2
2 3
2 4
1 5
.#
..
#.
.#
..
Q 5 3
C 1 ##
Q 4 5
Sample Output
3
数据规模
n<=30000 m<=80000
题解
折腾了俩个多小时+wa了好几次终于干掉了 T T
而且还好做过类似的线段树……
首先发现如果是一条链可以直接用一棵线段树
要记录一段左上到右上，左上到右下，左下到右上，左下到右下的最长距离
还要记录左上，左下，右上，右下出发能走的最长距离
这样合并大概十几行的样子
对于一棵树我们可以搞个树链剖分T T
但是还要注意x-lca(x,y)-y要将前半段反过来接上去才是正确的
剩下的就是代码能力的问题，像我这种傻×的话基本是不能1A的，所以如果是在考场上还需要暴力，对拍，数据生成器……总之，zjoi的题对于蒟蒻不可做 = =
而且我天生自带大常数T T（写的线段树什么狗屎样）
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 |
#include<iostream> #include<cstdio> #define inf 1000000000 #define N 30005 #define M 80005 using namespace std; inline 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-'0';ch=getchar();} return x*f; } int bin[25]; int n,m,cnt,place,sz; int last[N]; int deep[N],fa[N][16],son[N],belong[N],pl[N]; char mp[N][2]; struct data{int l1,l2,r1,r2,d1,d2,d3,d4;}; struct edge{int to,next;}e[2*N]; struct seg { int l,r;data d; }t[4*N]; void insert(int u,int v) { e[++cnt].to=v;e[cnt].next=last[u];last[u]=cnt; } //左上到右上，左上到右下，左下到右上，左下到右下 data merge(data a,data b) { data tmp; tmp.d1=max(a.d1+b.d1,a.d2+b.d3);if(tmp.d1<0)tmp.d1=-inf; tmp.d2=max(a.d1+b.d2,a.d2+b.d4);if(tmp.d2<0)tmp.d2=-inf; tmp.d3=max(a.d3+b.d1,a.d4+b.d3);if(tmp.d3<0)tmp.d3=-inf; tmp.d4=max(a.d3+b.d2,a.d4+b.d4);if(tmp.d4<0)tmp.d4=-inf; tmp.l1=max(a.d1+b.l1,a.d2+b.l2);tmp.l1=max(tmp.l1,a.l1);if(tmp.l1<0)tmp.l1=-inf; tmp.l2=max(a.d3+b.l1,a.d4+b.l2);tmp.l2=max(tmp.l2,a.l2);if(tmp.l2<0)tmp.l2=-inf; tmp.r1=max(b.d1+a.r1,b.d3+a.r2);tmp.r1=max(tmp.r1,b.r1);if(tmp.r1<0)tmp.r1=-inf; tmp.r2=max(b.d2+a.r1,b.d4+a.r2);tmp.r2=max(tmp.r2,b.r2);if(tmp.r2<0)tmp.r2=-inf; return tmp; } void build(int k,int l,int r) { t[k].l=l;t[k].r=r; if(l==r)return; int mid=(l+r)>>1; build(k<<1,l,mid);build(k<<1|1,mid+1,r); } void update(int k,int x,char mp[2]) { int l=t[k].l,r=t[k].r; if(l==r) { t[k].d.d1=t[k].d.d2=t[k].d.d3=t[k].d.d4=-inf; t[k].d.l1=t[k].d.l2=t[k].d.r1=t[k].d.r2=-inf; if(mp[0]=='.')t[k].d.d1=t[k].d.l1=t[k].d.r1=1; if(mp[1]=='.')t[k].d.d4=t[k].d.l2=t[k].d.r2=1; if(mp[0]=='.'&&mp[1]=='.') t[k].d.d2=t[k].d.d3=t[k].d.l1=t[k].d.l2=t[k].d.r1=t[k].d.r2=2; return; } int mid=(l+r)>>1; if(x<=mid)update(k<<1,x,mp); else update(k<<1|1,x,mp); t[k].d=merge(t[k<<1].d,t[k<<1|1].d); } data query(int k,int x,int y) { int l=t[k].l,r=t[k].r; if(x==l&&y==r)return t[k].d; int mid=(l+r)>>1; if(mid>=y) return query(k<<1,x,y); else if(mid<x) return query(k<<1|1,x,y); else return merge(query(k<<1,x,mid),query(k<<1|1,mid+1,y)); } void dfs1(int x) { son[x]=1; for(int i=1;i<=15;i++) if(deep[x]>=bin[i]) fa[x][i]=fa[fa[x][i-1]][i-1]; for(int i=last[x];i;i=e[i].next) { if(e[i].to==fa[x][0])continue; fa[e[i].to][0]=x; deep[e[i].to]=deep[x]+1; dfs1(e[i].to); son[x]+=son[e[i].to]; } } void dfs2(int x,int chain) { pl[x]=++place;belong[x]=chain; update(1,pl[x],mp[x]); int k=0; for(int i=last[x];i;i=e[i].next) { if(e[i].to==fa[x][0])continue; if(son[e[i].to]>son[k]) k=e[i].to; } if(k)dfs2(k,chain); for(int i=last[x];i;i=e[i].next) { if(e[i].to==k||e[i].to==fa[x][0])continue; dfs2(e[i].to,e[i].to); } } int lca(int x,int y) { if(deep[x]<deep[y])swap(x,y); int t=deep[x]-deep[y]; for(int i=0;i<=15;i++) if(bin[i]&t)x=fa[x][i]; for(int i=15;i>=0;i--) if(fa[x][i]!=fa[y][i]) x=fa[x][i],y=fa[y][i]; if(x==y)return x; return fa[x][0]; } data solveque(int x,int f,bool flag)//flag表示是否将f并进去 { data ans; ans.l1=ans.l2=ans.r1=ans.r2=0; ans.d1=ans.d4=ans.d2=ans.d3=0; while(belong[x]!=belong[f]) { ans=merge(query(1,pl[belong[x]],pl[x]),ans); x=fa[belong[x]][0]; } if(flag==1) { if(pl[f]+1<=pl[x])ans=merge(query(1,pl[f]+1,pl[x]),ans); } else ans=merge(query(1,pl[f],pl[x]),ans); return ans; } void que(int x,int y) { if(mp[x][0]=='#'&&mp[x][1]=='#'){printf("0\n");return;} int f=lca(x,y); data a=solveque(x,f,1),b=solveque(y,f,0); swap(a.d2,a.d3);swap(a.l1,a.r1);swap(a.l2,a.r2); data ans=merge(a,b); printf("%d\n",max(ans.l1,ans.l2)); } int main() { bin[0]=1;for(int i=1;i<=20;i++)bin[i]=(bin[i-1]<<1); int n=read();m=read(); for(int i=1;i<n;i++) { int u=read(),v=read(); insert(u,v);insert(v,u); } for(int i=1;i<=n;i++) scanf("%s",mp[i]); build(1,1,n); dfs1(1);dfs2(1,1); for(int i=1;i<=m;i++) { char ch[2];scanf("%s",ch); if(ch[0]=='Q') { int x=read(),y=read();que(x,y); } else { int x=read(); scanf("%s",mp[x]); update(1,pl[x],mp[x]); } } return 0; } |
OI 课件=>
蒟蒻求题解种所说的类似线段树题目。谢谢TAT！
【cf413E】Maze 2D