传送门

题目描述

像许多同龄的科学家和艺术家一样，小 L 对城市规划和城区设计很感兴趣.他致力于构建一个理想城。理想城由 N 个区块组成，而这些区块放在一个无限大的正方形网格上。第 x 行第 y 列的单元格由有序数对 (x,y)来标识。单元格 (0,0) 位于网格的左上角。给定一个单元格 (x,y)，与之相邻的单元格（如果存在的话）分别为：(x−1,y)，(x+1,y)，(x,y-1)，(x,y+1)。每个区块在网格上恰好覆盖一个单元格。一个区块能够被放置在单元格 (x,y) 上，当且仅当 1≤x,y≤2^31−2 。我们将使用单元格的坐标同时来代表单元格上面的区块。若两个区块被放在相邻的单元格中，则视它们为相邻区块.理想城所有的区块连在一起，里面没有“洞”存在.换言之，所有单元格必须满足下述两个条件：

  • 对于任意两个空白的单元格，至少存在一连串相邻的空白单元格连接它们。
  • 对于任意两个非空的单元格，至少存在一连串相邻的非空单元格连接它们。

以下 4个图中的区块放置均不满足理想城的条件。前两个图不满足第一个条件。第 3个图不满足第二个条件，第 4个图两个条件均不满足。

img

当遍历理想城时，一个跳步代表从一个区块走到一个相邻的区块。跳步时不能移进空白单元格。假设 v0,v1,⋯ ,vN−1v_0,v_1,\cdots,v_{N-1} 是 NN个区块的坐标。对于任意两个不同的区块 viv_i 和 vjv_j，它们的距离 d(vi,vj)d(v_i,v_j) 是从 viv_i移动到 vjv_j 所需的最小跳步数目。

下图是一个由 1 个区块组成的理想城。区块坐标分别为

v0=(2,5)v1=(2,6)v2=(3,3)v3=(3,6)v4=(4,3)v5=(4,4)v6=(4,5)v7=(4,6)v8=(5,3)v9=(5,4)v10=(5,6)v_0=(2,5) \quad v_1=(2,6) \quad v_2=(3,3) \\ v_3=(3,6) \quad v_4=(4,3) \quad v_5=(4,4) \\ v_6=(4,5) \quad v_7=(4,6) \quad v_8=(5,3) \\ v_9=(5,4) \quad v_{10}=(5,6)

其中，d(v1,v3)=1d(v_1,v_3)=1，d(v1,v8)=6d(v_1,v_8)=6，d(v6,v10)=2d(v_6,v_10)=2，d(v9,v10)=4d(v_9,v_10)=4。

给定一个理想域，试求

S=∑i=0N−2∑j=i+1N−1d(vi,vj)S=\sum_{i=0}^{N-2}\sum_{j=i+1}^{N-1}d(v_i,v_j)

输入格式

第 11 行为一个正整数 NN，为理想城区块的数目。

第 22 行到第 N+1N+1 行，每行有两个非负整数。第 i+2i+2 行为第 ii 个区块的坐标 vi=(xi，yi)v_i = (x_i， y_i)。

输出格式

输出仅一行一个正整数，为 SS 的值。由于 SS 的值可能较大，你只需输出 SS 对 10910^9 取模的值。

输入数据 1

1
2
3
4
5
6
7
8
9
10
11
12
11
2 5
2 6
3 3
3 6
4 3
4 4
4 5
4 6
5 3
5 4
5 6

输出数据 1

1
174

提示

对于 100%100\%的数据，1≤N≤1051 \le N \le 10^5，1≤xi,yi≤231−21 \le x_i,y_i \le 2^{31}-2。

题解

先对每一个点进行关键字排序

  • 以xx为第一关键字，yy为第二关键字排序
  • 以yy为第一关键字，xx为第二关键字排序

首先横着看，把每一行相连的块视为一个值为连续块个数的节点

那么图就变成了这个样子

此时可以发现，每一层与下一层之间通过的贡献就是这一层上面节点之和×\times下面的节点之和

由此可以类比每一列

代码

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
#include <cstdio>
#include <algorithm>
#define N 100005
#define MOD 1000000000
using namespace std;
struct Pos {long long x,y;} a[N];
struct Block {long long l,r;} b[N];
struct Edge {long long to,nxt;} e[N<<1];
long long tot,n,fs[N],fir[N],dep,cnt;long long ans;
bool cmp1(Pos x,Pos y) {return x.x==y.x?x.y<y.y:x.x<y.x;}
bool cmp2(Pos x,Pos y) {return x.y==y.y?x.x<y.x:x.y<y.y;}
void add(long long u,long long v) {e[++tot]=(Edge){v,fs[u]},fs[u]=tot;}
long long getans(long long i,long long d)
{
	long long sum=b[i].r-b[i].l+1;
	for (long long j=fs[i];j;j=e[j].nxt)
		if (e[j].to!=d) sum+=getans(e[j].to,i);
	return ans+=sum*(n-sum)%MOD,ans%=MOD,sum;
}
int main()
{
	freopen("city.in","r",stdin);
	freopen("city.out","w",stdout);
	scanf("%lld",&n);
	for (long long i=1;i<=n;++i)
		scanf("%lld",&a[i].x),
			scanf("%lld",&a[i].y);
	sort(a+1,a+n+1,cmp1);
	b[cnt=dep=0]=(Block){-0x3f3f,-0x3f3f};
	for (long long i=1;i<=n;++i)
	{
		if (a[i].x!=a[i-1].x) fir[++dep]=cnt+1;
		if (a[i].y!=b[cnt].r+1)
			b[++cnt]=(Block){a[i].y,a[i].y};
		else b[cnt].r=a[i].y;
	}fir[dep+1]=n+1;
	for (long long i=1;i<dep;++i)
	{
		long long j=i+1,t1=fir[i],t2=fir[j];
		while (t1<fir[j]&&t2<fir[j+1])
			if (b[t1].r<b[t2].l) ++t1;
			else if (b[t2].r<b[t1].l) ++t2;
			else {
				add(t1,t2),add(t2,t1);
				if (t1<fir[j]-1&&b[t1+1].l<=b[t2].r)
					++t1; else ++t2;
			}
	}getans(1,0);
	sort(a+1,a+n+1,cmp2);
	for (long long i=1;i<=n;++i) fs[i]=fir[i]=0,b[i]=(Block){0,0};
	for (int i=1;i<=tot;++i) e[i]=(Edge){0,0};
	cnt=dep=tot=0;
	for (long long i=1;i<=n;++i)
	{
		if (a[i].y!=a[i-1].y) fir[++dep]=cnt+1;
		if (a[i].x!=b[cnt].r+1)
			b[++cnt]=(Block){a[i].x,a[i].x};
		else b[cnt].r=a[i].x;
	}fir[dep+1]=n+1;
	for (long long i=1;i<dep;++i)
	{
		long long j=i+1,t1=fir[i],t2=fir[j];
		while (t1<fir[j]&&t2<fir[j+1])
			if (b[t1].r<b[t2].l) ++t1;
			else if (b[t2].r<b[t1].l) ++t2;
			else {
				add(t1,t2),add(t2,t1);
				if (t1<fir[j]-1&&b[t1+1].l<=b[t2].r)
					++t1; else ++t2;
			}
	}getans(1,0);
	printf("%lld",ans);
}