jzoj3738-[NOI2014 simulation 7.11] ideal city (city) [tree, model transformation]

Topic

The main idea of the topic

An ideal city consists of nnn blocks with the following properties

  1. Any two blocks can be reached by other blocks.
  2. Any two blocks can be reached between them without other blocks (via vacancies)

Then the sum of the distances between each block is obtained.

Solving problems

We calculate the vertical and horizontal distances separately.

Assuming that we now consider calculating the distance between vertical edges, we reduce the transverse contiguous blocks to a point (as shown below).

Then the two adjacent blocks are connected to each other so that, because of the above properties, the tree structure can be guaranteed. Then calculate how many times each side corresponds to these numbers in total. That is to say, for every edge of x_gt; yx-> yx_ > y, there are (n_sizey)sizey(n-size_y)*size_y(n_sizey) sizey.

Then, add up the answers one time by one time.

codecodecode

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<map>
#define p(x,y) ((x-1)*m+y)
using namespace std;
const int N=100100,XJQ=1e9+7;
struct node{
	int x,y;
}w[N];
struct edge_node{
	int to,next;
}a[N*2];
struct seq_node{
	int l,r,num;
}seq[N];
map<int,int> bz[N];
int n,bx,mx,p[N],cnt,ans,size[N],ls[N],tot;
bool cmp(node x,node y)
{return x.x==y.x?x.y<y.y:x.x<y.x;}
void adde(int x,int y)
{
	if(a[ls[x]].to==y) return;
	a[++tot].to=y;
	a[tot].next=ls[x];
	ls[x]=tot;
}
void dp(int x,int fa)
{
	for(int i=ls[x];i;i=a[i].next)
	{
		int y=a[i].to;
		if(y==fa) continue;
		dp(y,x);
		size[x]+=size[y];
	}
	for(int i=ls[x];i;i=a[i].next)
	{
		int y=a[i].to;
		if(y==fa) continue;
		ans=(ans+(size[y]*(n-size[y]))%XJQ)%XJQ;
	}
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		scanf("%d%d",&w[i].x,&w[i].y),bx=min(bx,w[i].x),by=min(my,w[i].y);
	sort(w+1,w+1+n,cmp);
	for(int i=1;<=n;i++){
		w[i].x-=bx-1,w[i].y-=by-1;
		bz[p(w[i].x,w[i].y)]=i;
	}
	for(int i=1;i<=n;i++){
		int x=w[i].x,y=w[i].y;
		if(be[i]==0){
			be[i]=1;size[i]=1;
			for(int j=i-1;i>=1;i--)
				if(p[j].y==p[j+1].y+1) be[j]=i,size[j]++;
				else break;
		}
		int k=bz[p(x,y)];
		if(bz.find(p(x,y))!=bz.end())
			adde(be[k],be[i]),adde(be[i],be[k]);
	}
	printf("%d",ans);
}

Posted on Tue, 08 Oct 2019 02:04:36 -0700 by ziola