Educational Codeforces Round 138 E,F

E
一道比较基础的题。

首先就是纵向，走无障碍的格子，无法四联通和横向，走有障碍的格子，八联通是等价的。

也就是，如果我们要让其不存在非法路径，那么应该存在一个从第一列出发，一路都是#的八联通路径，并且根据题意，仙人掌不能上下左右相邻，那么就是右上、右下、左上、左下的四个方向的路径。

那么我们可以在某些点将'.'换成'#'（注意这个点四周不能有'#'），并且“路径”长度加一。

也就是可以01 BFS解决。

F
一道十分有趣的题。

首先我们直接找所有距离路径不超过\(d\)的点是没戏的。

考虑只更新链。在查询时，我们从当前点\(x\)一路往上跳，并且将\(d\)从\(0\)一路相加到\(20\)为止。

更新时，我们要给路径上每个点在一个下标处\(+k\)，使得查询时没有重复计算。

所以，我们能构造出下图左侧的方法，也就是\(x\)到\(y\)路径上的tag为\(d\)，\(lca\)往上分别是\(d-1\)到\(0\)。

但是我们发现一个问题，比如中间的情况，我们查询（红线）往上跳时，正好“错过”了我们修改，也就是交点在两个节点中间，这种情况会出现漏统计。

不过很幸运，只有这一种情况会出错。

于是我们稍作修改，得到右侧的打\(tag\)方式，就是对于\(lca\)和往上的点，分别将\(i\)和\(i-1\)加入，这样就不用担心交点在中间了，并且其余的路径交点个数也是\(1\)。

可以用树链剖分进行路径修改，时间复杂度为\(O(n(\log n+d)\log n)\)。

这里附上两题代码：
E

#include<bits/stdc++.h>
#define debug(...) std::cerr<<#__VA_ARGS__<<" : "<<__VA_ARGS__<<std::endl

const int maxn=400005;

const int dx[]={-1,1,1,-1,0,0,-1,1};
const int dy[]={1,-1,1,-1,-1,1,0,0};

int n,m,dist[maxn],from[maxn],vis[maxn],cant[maxn];
char buf[maxn];
std::vector<std::pair<int,int>> G[maxn];

int main() {
	int T;
	scanf("%d",&T);
	while(T--) {
		scanf("%d%d",&n,&m);
		std::vector<int> a(1,0);
		std::vector<std::vector<int>> id(n+5,std::vector<int>(m+5,0));
		for(int i=1;i<=n;i++) {
			scanf("%s",buf+1);
			for(int j=1;j<=m;j++) {
				id[i][j]=a.size();
				a.push_back(buf[j]=='#'?1:0);
			}
		}
		for(int i=1;i<=n*m;i++) {
			G[i].clear();
			cant[i]=0;
		}
		for(int i=1;i<=n;i++) {
			for(int j=1;j<=m;j++) {
				if(a[id[i][j]]==1) {
					for(int k=4;k<8;k++) {
						int i_=i+dx[k],j_=j+dy[k];
						if(i_<1||j_<1||i_>n||j_>m) continue;
						cant[id[i_][j_]]=1;
					}
				}
			}
		}
		for(int i=1;i<=n;i++) {
			for(int j=1;j<=m;j++) {
				if(cant[id[i][j]]) continue;
				for(int k=0;k<4;k++) {
					int i_=i+dx[k],j_=j+dy[k];
					if(i_<1||j_<1||i_>n||j_>m||cant[id[i_][j_]]) continue;			
					G[id[i][j]].push_back({id[i_][j_],1-a[id[i_][j_]]});
				}
			}
		}
		std::deque<int> q;
		for(int i=1;i<=n*m;i++) dist[i]=1e9,from[i]=-1,vis[i]=0;
		for(int i=1;i<=n;i++) {
			if(a[id[i][1]]) q.push_front(id[i][1]),dist[id[i][1]]=0;
			else q.push_back(id[i][1]),dist[id[i][1]]=1;
		}
		while(!q.empty()) {
			int pos=q.front(); q.pop_front();
			if(vis[pos]) continue;
			vis[pos]=1;
			for(auto nxt : G[pos]) {
				if(dist[nxt.first]>dist[pos]+nxt.second) {
					dist[nxt.first]=dist[pos]+nxt.second;
					from[nxt.first]=pos;
					if(nxt.second) q.push_back(nxt.first);
					else q.push_front(nxt.first);
				}
			}
		}
		int start=-1,ans=1e9;
		for(int i=1;i<=n;i++) {
			if(dist[id[i][m]]<ans) {
				ans=dist[id[i][m]];
				start=id[i][m];
			}
		}
		if(ans==1e9) {
			printf("NO\n");
			continue;
		}
		printf("YES\n");
		while(start!=-1) {
			if(!a[start]) a[start]=1;
			start=from[start];
		}
		for(int i=1;i<=n;i++) {
			for(int j=1;j<=m;j++) {
				printf("%c",a[id[i][j]]?'#':'.');
			}
			printf("\n");
		} 
	} 
	return 0;
}

F

#include<bits/stdc++.h>
#define debug(...) std::cerr<<#__VA_ARGS__<<" : "<<__VA_ARGS__<<std::endl

const int maxn=200105;

int n,q;
int cnt,id[maxn],siz[maxn],son[maxn],top[maxn],father[maxn],dep[maxn];
std::vector<int> G[maxn];

void dfs(int pos,int fa,int depth) {
	siz[pos]=1,father[pos]=fa,dep[pos]=depth;
	for(int i=0,temp=-1;i<(int)G[pos].size();i++) {
		int to=G[pos][i]; if(to==fa) continue;
		dfs(to,pos,depth+1); siz[pos]+=siz[to];
		if(siz[to]>temp) temp=siz[to],son[pos]=to;
	}
}
 
void dfs2(int pos,int fa,int tp) {
	id[pos]=++cnt; top[pos]=tp;
	if(son[pos]) dfs2(son[pos],pos,tp);
	for(int i=0;i<(int)G[pos].size();i++) {
		int to=G[pos][i];
		if(to!=fa&&to!=son[pos]) dfs2(to,pos,to);
	}
}

struct bit {
	int val[maxn];
	#define lowbit(x) (x&-x)
	void update(int l,int r,int num) {
		for(int i=l;i<maxn;i+=lowbit(i)) val[i]+=num;
		for(int i=r+1;i<maxn;i+=lowbit(i)) val[i]-=num;
	}
	int query(int x) {
		int ret=0;
		for(int i=x;i;i-=lowbit(i)) ret+=val[i];
		return ret;
	}
}tree[25];

void upath(int x,int y,int num,int d) {
	while(top[x]!=top[y]) {
		if(dep[top[x]]<dep[top[y]]) std::swap(x,y);
		tree[d].update(id[top[x]],id[x],num);
		x=father[top[x]];
	}
	if(dep[x]>dep[y]) std::swap(x,y);
	tree[d].update(id[x]+1,id[y],num);
	for(;d>=0;d--,x=father[x]) {
		tree[d].update(id[x],id[x],num);
		if(d) tree[d-1].update(id[x],id[x],num);
	}
}

int qnode(int x) {
	int ans=0;
	for(int d=0;d<=20;d++,x=father[x]) {
		ans+=tree[d].query(id[x]);
	}
	return ans;
}

int main() {
	scanf("%d",&n);
	for(int i=1;i<n;i++) {
		int x,y; scanf("%d%d",&x,&y);
		G[x].push_back(y);
		G[y].push_back(x);
	}
	int root=n+25;
	G[n+1].push_back(1);
	G[1].push_back(n+1);
	for(int i=n+2;i<=n+30;i++) {
		G[i].push_back(i-1);
		G[i-1].push_back(i);
	}
	//root
	dfs(root,0,1); dfs2(root,0,root);
	scanf("%d",&q);
	while(q--) {
		int opt,x,y,k,d;
		scanf("%d",&opt);
		if(opt==1) {
			scanf("%d",&x);
			printf("%d\n",qnode(x));
			
		} else {
			scanf("%d%d%d%d",&x,&y,&k,&d);
			upath(x,y,k,d);
		}
	}
	return 0;
}