【CodeChef】Querying on a Grid（分治，最短路）

时间：2022-04-28 17:10:04

【CodeChef】Querying on a Grid（分治，最短路）

题面

Vjudge

CodeChef

题解

考虑分治处理这个问题，每次取一个\(mid\)，对于\(mid\)上的三个点构建最短路径树(因为保证了最短路唯一所以是树)。

如果两点之间的最短路径跨越了\(mid\)，那么必定有\(dis[u]+dis[v]\)的和就是最短路径长度。

那么我们在分治过程中考虑每一个\(mid\)，取其中\(dis[u]+dis[v]\)的最小值，这样子就很容易可以找到最短路径长度。

然后知道了最短路径长度怎么找到最短路径呢？

我们已经把最短路径树给构出来了，那么只需要在必定跨越的\(mid\)的最短路径树上做修改就好了。

如果直接链加再单点询问，这样子是两个\(log\)的，改成单点修改，子树求和就可以做到一个\(log\)了。

这样子分治+对于每个最短路径树计算答案，复杂度是\(O(nlog^2n)\)，似乎还有一个\(3\)的常数。

c++11真好用，写着写着就跟zsy代码一样了（大雾

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<cmath>

#include<algorithm>

#include<vector>

#include<queue>

using namespace std;

#define ll long long

#define MAX 300300

#define pi pair<ll,int>

#define fr first

#define sd second

#define mp make_pair

#define pb push_back

inline ll read()

{

	ll x=0;bool t=false;char ch=getchar();

	while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();

	if(ch=='-')t=true,ch=getchar();

	while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();

	return t?-x:x;

}

vector<pi> E[MAX];

int n,m,Q;

int id[MAX][3],tot;

int lb(int x){return x&(-x);}

struct SPT

{

	ll dis[MAX],c[MAX];int fa[MAX],dfn[MAX],low[MAX],tim;

	bool vis[MAX];

	vector<int> son[MAX];

	priority_queue<pi,vector<pi>,greater<pi> >Q;

	void dfs(int u){dfn[u]=++tim;for(int v:son[u])dfs(v);low[u]=tim;}

	void Modify(int x,ll w){x=dfn[x];while(x<=tim)c[x]+=w,x+=lb(x);}

	ll Query(int x)

	{

		ll ret=0;int X;

		X=low[x];while(X)ret+=c[X],X-=lb(X);

		X=dfn[x]-1;while(X)ret-=c[X],X-=lb(X);

		return ret;

	}

	void Dijkstra(int l,int r,int S)

	{

		for(int i=l;i<=r;++i)dis[i]=1e18,vis[i]=false;

		dis[S]=0;Q.push(mp(dis[S],S));

		while(!Q.empty())

		{

			int u=Q.top().sd;Q.pop();

			if(vis[u])continue;vis[u]=true;

			for(pi x:E[u])

			{

				int v=x.sd;ll w=x.fr;

				if(v<l||v>r||dis[v]<=dis[u]+w)continue;

				dis[v]=dis[u]+w;fa[v]=u;Q.push(mp(dis[v],v));

			}

		}

		for(int i=l;i<=r;++i)if(i!=S)son[fa[i]].pb(i);

		dfs(S);

	}

}T[18][3];

void Build(int l,int r,int dep)

{

	int mid=(l+r)>>1;

	for(int i=0;i<n;++i)

		T[dep][i].Dijkstra(id[l][0],id[r][n-1],id[mid][i]);

	if(l<mid)Build(l,mid-1,dep+1);

	if(r>mid)Build(mid+1,r,dep+1);

}

ll mx;

void Calc(int l,int r,int dep,int x,int y)

{

	int mid=(l+r)>>1;

	for(int i=0;i<n;++i)

		mx=min(mx,T[dep][i].dis[x]+T[dep][i].dis[y]);

	if(x<=id[mid][n-1]&&y>=id[mid][0])return;

	if(y<id[mid][0])Calc(l,mid-1,dep+1,x,y);

	else Calc(mid+1,r,dep+1,x,y);

}

void Modify(int l,int r,int dep,int x,int y,ll w)

{

	int mid=(l+r)>>1;

	for(int i=0;i<n;++i)

		if(T[dep][i].dis[x]+T[dep][i].dis[y]==mx)

		{

			T[dep][i].Modify(x,w),T[dep][i].Modify(y,w);

			return;

		}

	if(y<id[mid][0])Modify(l,mid-1,dep+1,x,y,w);

	else Modify(mid+1,r,dep+1,x,y,w);

}

ll Query(int l,int r,int dep,int u)

{

	int mid=(l+r)>>1;ll ret=0;

	for(int i=0;i<n;++i)

	{

		ll s=T[dep][i].Query(u);

		if(id[mid][i]==u)s>>=1;

		ret+=s;

	}

	if(u<id[mid][0])ret+=Query(l,mid-1,dep+1,u);

	if(u>id[mid][n-1])ret+=Query(mid+1,r,dep+1,u);

	return ret;

}

int main()

{

	n=read();m=read();Q=read();

	for(int i=0;i<m;++i)

		for(int j=0;j<n;++j)id[i][j]=++tot;

	for(int i=0;i<n-1;++i)

		for(int j=0;j<m;++j)

		{

			int u=id[j][i],v=id[j][i+1];ll w=read();

			E[u].pb(mp(w,v));E[v].pb(mp(w,u));

		}

	for(int i=0;i<n;++i)

		for(int j=0;j<m-1;++j)

		{

			int u=id[j][i],v=id[j+1][i];ll w=read();

			E[u].pb(mp(w,v));E[v].pb(mp(w,u));

		}

	Build(0,m-1,0);

	while(Q--)

	{

		int opt=read();

		if(opt==1)

		{

			int x1=read()-1,y1=read()-1,x2=read()-1,y2=read()-1;ll w=read();

			int u=id[y1][x1],v=id[y2][x2];if(u>v)swap(u,v);

			mx=1e18;Calc(0,m-1,0,u,v);

			Modify(0,m-1,0,u,v,w);

		}

		else

		{

			int x=read()-1,y=read()-1,u=id[y][x];

			printf("%lld\n",Query(0,m-1,0,u));

		}

	}

	return 0;

}

相关文章