QOJ4887 Fast Bridge 题解

First Post:

Last Update:

想题的过程中，正解的每个部分都想到了，但没有将其统一起来。说明在想题的时候，需要回顾之前的思路，看是否能结合起来产生新的想法。

发现走一座桥顶多会使代价 ，所以要保证走这座桥时，“必须朝着终点走”。以两个点 为例。如果我们要从 走到 ，那么只会走 的桥，反之，如果 ，那么只会走 的桥。

为了计算答案方便，我们设 表示在上述条件下从 到 经过的最多的桥数。那么答案就是所有点的曼哈顿距离之和 （其等于 ) 减去所有的 之和。

所以我们先将所有 的桥提出来，算所有 的点对的贡献。

先将所有桥按 排序，然后定义 表示从第 座桥的起点走到第 座桥的终点，最多会经过多少座桥。枚举中转点 DP 可以做到 。

然后我们从大到小枚举 ，从大到小枚举 ，考虑计算 对其右上方点的贡献。计算这个贡献显然还是需要考察桥，所以设 表示从 出发，走到第 座桥的终点，最多能经过多少座桥。首先 可以从 和 转移。其次，如果一座桥 的起点为 ，那么 。

考虑知道了 之后怎么算贡献。我们枚举数值 ，计算 ，但这并不好算，改为计算 。可以找到所有 的桥 ，那么对于 的点 ，都有 。所以此时我们要计算一些 2-side 矩形的面积并。我们将所有桥按 升序插入，维护一个变量 表示当前最小的 ，如果当前的 不小于 ，那么没有任何新的贡献产生，否则会有一个长为 ，宽为 的新矩形区域进入答案，加上这个矩形的面积后，将 即可。

但是如果对每个 ，都把 的桥遍历一遍，对于单个 的复杂度就是 的。但是我们发现，如果一个 ，那么肯定存在一个 使得 且 。所以 能产生的贡献完全被 包含，我们就不用考虑 了。所以对于一个 ，只用算所有 的桥即可。对于单个 的复杂度就是 的了。

所以总时间复杂度为 ，空间复杂度可以用滚动数组优化到 。

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
#include <bits/stdc++.h>
using namespace std;
const int N = 5e2 + 5,P = 998244353,inv3 = (P + 1) / 3;
typedef pair<int,int> pii;
#define FI first
#define SE second
inline void Plus(int &x,const int &y) { x += y;if(x >= P) x -= P;}
template<typename T> inline void ckmax(T &x,const T &y) { (x < y) && (x = y);}
int n,K;

struct Bridge {
	int x1,y1,x2,y2;
	Bridge(){}
	bool operator < (const Bridge &rhs) const { return x2 < rhs.x2;}
};
Bridge p[N];
inline bool Trans1(const Bridge &i,const Bridge &j) {
	return i.x2 <= j.x1 && i.y2 <= j.y1;
}
inline bool Trans2(const Bridge &i,const Bridge &j) {
	return i.x2 <= j.x1 && i.y2 >= j.y1;
}
int dp[N][N];
int val1[N << 1],len1;
int val2[N << 1],len2;
int f[2][N << 1][N]; // f_{x,y,i}

 // x2 升序
vector<int> brs[N << 1][N << 1];
int Area[N]; // 2-side 矩形面积并
int LowY[N]; // Y 的最值

Bridge p1[N],p2[N];
int n1,n2;

inline int Solve1() {
	for(int i = 1;i <= n1;i++)
		for(int j = 1;j <= n1;j++) dp[i][j] = 0;
	for(int i = 1;i <= n1;i++) dp[i][i] = 1;
	for(int len = 2;len <= n1;len++)
		for(int i = 1;i + len - 1 <= n1;i++) {
			int j = i + len - 1;
			if(!Trans1(p1[i],p1[j])) continue;
			dp[i][j] = 2;
			for(int k = i + 1;k < j;k++)
				if(Trans1(p1[i],p1[k]) && Trans1(p1[k],p1[j]))
					dp[i][j] = max(dp[i][j],dp[i][k] + dp[k][j] - 1);
		}
	for(int i = 1;i <= len1;i++)
		for(int j = 1;j <= len2;j++) brs[i][j].clear();
	for(int i = 1;i <= n1;i++)
		brs[p1[i].x1][p1[i].y1].push_back(i);
	memset(f,0,sizeof f); 
	int ans = 0;
	for(int x = len1 - 1;x >= 1;x--) {
		for(int y = len2 - 1;y >= 1;y--) {
			for(int i = 1;i <= n1;i++) {
				f[x & 1][y][i] = max(f[x & 1][y + 1][i],f[(x+1) & 1][y][i]);
				for(auto id : brs[x][y])
					ckmax(f[x & 1][y][i],dp[id][i]);
			}
			int tmp = 0;
			for(int i = 1;i <= n1;i++) LowY[i] = K + 1;
			for(int i = 1;i <= n1;i++) {
				int u = f[x & 1][y][i];
				if(!u) continue;
				if(val2[p1[i].y2] < LowY[u])
					Plus(tmp,1ll * (LowY[u] - val2[p1[i].y2]) * (K + 1 - val1[p1[i].x2]) % P),
					LowY[u] = val2[p1[i].y2];
			}
			Plus(ans,1ll * tmp * (val1[x] - val1[x - 1]) % P * (val2[y] - val2[y - 1]) % P);
		}
	}
	// printf("ans:%d\n",ans);
	return ans;
}
inline int Solve2() {
	for(int i = 1;i <= n2;i++) for(int j = 1;j <= n2;j++) dp[i][j] = 0;
	for(int i = 1;i <= n2;i++) dp[i][i] = 1;
	for(int len = 2;len <= n2;len++)
		for(int i = 1;i + len - 1 <= n2;i++) {
			int j = i + len - 1;
			if(!Trans2(p2[i],p2[j])) continue;
			dp[i][j] = 2; 
			for(int k = i + 1;k < j;k++)
				if(Trans2(p2[i],p2[k]) && Trans2(p2[k],p2[j]))
					dp[i][j] = max(dp[i][j],dp[i][k] + dp[k][j] - 1);
		}
	for(int i = 1;i <= len1;i++)
		for(int j = 1;j <= len2;j++)
			brs[i][j].clear();
	for(int i = 1;i <= n2;i++)
		brs[p2[i].x1][p2[i].y1].emplace_back(i);
	memset(f,0,sizeof f);
	int ans = 0;
	for(int x = len1 - 1;x >= 1;x--) {
		for(int y = 1;y < len2;y++) {
			for(int i = 1;i <= n2;i++) {
				f[x & 1][y][i] = max(f[(x+1)&1][y][i],f[x & 1][y - 1][i]);
				for(auto id : brs[x][y])
					ckmax(f[x & 1][y][i],dp[id][i]);
			}
			int tmp = 0;
			for(int i = 1;i <= n2;i++) LowY[i] = 0;
			for(int i = 1;i <= n2;i++) {
				int u = f[x & 1][y][i];
				if(!u) continue;
				if(val2[p2[i].y2] > LowY[u])
					Plus(tmp,1ll * (val2[p2[i].y2] - LowY[u]) * (K + 1 - val1[p2[i].x2]) % P),
					LowY[u] = val2[p2[i].y2];
			}
			Plus(ans,1ll * tmp * (val1[x] - val1[x - 1]) % P * (val2[y + 1] - val2[y]) % P);
		}
	}
	return ans;
}
int main() {
	cin >> n >> K;
	for(int i = 1;i <= n;i++)
		cin >> p[i].x1 >> p[i].y1 >> p[i].x2 >> p[i].y2;
	sort(p + 1,p + n + 1);
	for(int i = 1;i <= n;i++) val1[++len1] = p[i].x1,val1[++len1] = p[i].x2;
	val1[++len1] = K + 1;
	sort(val1 + 1,val1 + len1 + 1);
	len1 = unique(val1 + 1,val1 + len1 + 1) - val1 - 1;
	for(int i = 1;i <= n;i++) val2[++len2] = p[i].y1,val2[++len2] = p[i].y2;
	val2[++len2] = K + 1;
	sort(val2 + 1,val2 + len2 + 1);
	len2 = unique(val2 + 1,val2 + len2 + 1) - val2 - 1;
	auto idX = [&](const int &t) { return lower_bound(val1 + 1,val1 + len1 + 1,t) - val1;};
	auto idY = [&](const int &t) { return lower_bound(val2 + 1,val2 + len2 + 1,t) - val2;};
	for(int i = 1;i <= n;i++)
		p[i].x1 = idX(p[i].x1),p[i].x2 = idX(p[i].x2),
		p[i].y1 = idY(p[i].y1),p[i].y2 = idY(p[i].y2);
	for(int i = 1;i <= n;i++)
		if(p[i].y1 < p[i].y2) p1[++n1] = p[i];
		else p2[++n2] = p[i];
	int ans = 1ll * K * K % P * K % P * K % P * (K + 1) % P;
	Plus(ans,P - 1ll * K * K % P * K % P * (K + 1) % P * (K + K + 1) % P * inv3 % P);
	Plus(ans,P - Solve1());
	Plus(ans,P - Solve2());
	cout << ans << endl;
	return 0;
}
≡