计蒜客微软大楼设计方案（RMQ）

中文题就不说题意了~

首先是简单版本

满足$1 <= n, m <= 50$

那么设$c[i][j]$为从第$i$幢楼到第$j$幢楼的最低的那幢楼的高度

计算两个点之间的距离的时候，若两个点分别在第$i$列，第$j$列，那么要根据$c[i][j]$来计算。

暴力即可

#include <bits/stdc++.h>

using namespace std;

#define rep(i, a, b)	for (int i(a); i <= (b); ++i)

#define dec(i, a, b)	for (int i(a); i >= (b); --i)

int n, k;

int a[10010];

int c[201][201];

int x[201], y[201];

int m;

int ans = 0;

int main(){

	scanf("%d%d", &n, &k);

	rep(i, 1, n) scanf("%d", a + i);

	rep(i, 1, n){

		c[i][i] = a[i];

		rep(j, i + 1, n) c[i][j] = min(c[i][j - 1], a[j]), c[j][i] = c[i][j];

	}

	rep(i, 1, n) rep(j, 1, n) if (c[i][j] == 0) c[i][j] = c[j][i];

	scanf("%d", &m);

	rep(i, 1, m) scanf("%d%d", x + i, y + i);

	rep(i, 1, m - 1){

		rep(j, i + 1, m){

			int cnt;

			if (y[i] > c[x[i]][x[j]] && y[j] > c[x[i]][x[j]])

				cnt = y[i] - c[x[i]][x[j]] + y[j] - c[x[i]][x[j]] + abs(x[i] - x[j]);

			else cnt = abs(x[i] - x[j]) + abs(y[i] - y[j]);

			if (cnt <= k) ++ans;

		}

	}

	printf("%d\n", ans);

	return 0;

}

再是中等版本

满足$1 <= n <= 200000, 1 <= m <= 2000$

$m$的范围让我们还是可以在1秒钟之内两两枚举点对并完成统计

就是$c[i][j]$不能按照刚刚那个方法求了。

我们构建一张ST表，令$f[i][j]$为从$i$开始连续$2^{j}$个数的最小值

于是在$O(1)$内我们可以得到第$i$幢楼到第$j$幢楼的最低的那幢楼的高度

中等版本也解决了

#include <bits/stdc++.h>

using namespace std;

#define rep(i, a, b)	for (int i(a); i <= (b); ++i)

#define dec(i, a, b)	for (int i(a); i >= (b); --i)

int a[200030];

int f[200030][22];

int n, m, k;

int ans = 0;

struct node{

	int x, y;

	void scan(){ scanf("%d%d", &x, &y);}

	friend bool operator < (const node &a, const node &b){

		return a.x == b.x ? a.y < b.y : a.x < b.x;

	}

} p[3010];

inline int solve(int l, int r){

	int k = (int)log2((double)(r - l + 1));

	return min(f[l][k], f[r - (1 << k) + 1][k]);

}

void work(){

	rep(i, 1, n) f[i][0] = a[i];

	rep(j, 1, 20) rep(i, 1, n)

		if ((i + (1 << j) - 1) <= n) f[i][j] = min(f[i][j - 1], f[i + (1 << (j - 1))][j - 1]);

}

int main(){

	scanf("%d%d", &n, &k);

	rep(i, 1, n) scanf("%d", a + i);

	work();

	scanf("%d", &m);

	rep(i, 1, m) p[i].scan();

	sort(p + 1, p + m + 1);

	rep(i, 1, m - 1){

		rep(j, i + 1, m){

			int cnt;

			int now = solve(p[i].x, p[j].x);

			if (p[i].y > now && p[j].y > now)

				cnt = p[i].y - now + p[j].y - now + abs(p[i].x - p[j].x);

			else cnt = abs(p[i].x - p[j].x) + abs(p[i].y - p[j].y);

			if (cnt <= k) ++ans;

		}

	}

	printf("%d\n", ans);

	return 0;

}

最后是困难版本

满足$1 <= n <= 200000, 1 <= m <= 200000$

这个时候不能两两枚举点对来统计了

注意到$h[i] <= 20$，这是一个很重要的条件

对于当前在第$i$列的某个点，我们发现在他之后的$max(0, k - 40)$列中的所有点

这些点不用考虑，一定符合条件

因位距离最大值为$ k - 40 + max(h[i]) + max(h[j]) <= k$，所以一定符合条件

同理我们也发现，第$i + k$之后的点肯定不符合条件

那么我们只要枚举$i + max(0, k - 40) + 1$ 到 $i + k$ 这些列中的所有点就可以了

做的时候维护一个前缀和即可。

时间复杂度$O(mlogm + mh^{2})$

#include <bits/stdc++.h>

using namespace std;

#define rep(i, a, b)	for (int i(a); i <= (b); ++i)

#define dec(i, a, b)	for (int i(a); i >= (b); --i)

const int N = 200100;

int a[N];

int f[N][22];

int n, m, k;

long long ans = 0;

long long c[N];

int g[N][22];

vector <int> v[N];

struct node{

	int x, y;

	void scan(){ scanf("%d%d", &x, &y);}

	friend bool operator < (const node &a, const node &b){

		return a.x == b.x ? a.y < b.y : a.x < b.x;

	}

} p[N];

inline int solve(int l, int r){

	int k = (int)log2((double)(r - l + 1));

	return min(f[l][k], f[r - (1 << k) + 1][k]);

}

void work(){

	rep(i, 1, n) f[i][0] = a[i];

	rep(j, 1, 20) rep(i, 1, n)

		if ((i + (1 << j) - 1) <= n) f[i][j] = min(f[i][j - 1], f[i + (1 << (j - 1))][j - 1]);

}

int main(){

	scanf("%d%d", &n, &k);

	rep(i, 1, n) scanf("%d", a + i);

	work();

	scanf("%d", &m);

	rep(i, 1, m) p[i].scan();

	sort(p + 1, p + m + 1);

	memset(g, 0, sizeof g);

	rep(i, 1, m) ++c[p[i].x];

	rep(i, 1, n) c[i] += c[i - 1];

	rep(i, 1, m){

		v[p[i].x].push_back(i);

		g[p[i].x][p[i].y] = 1;

	}

	rep(i, 1, m){

		rep(j, p[i].y + 1, a[p[i].x]) if (abs(j - p[i].y) <= k && g[p[i].x][j]) ++ans;

		int cnt = p[i].x + k - 40;

		if (cnt > n) cnt = n;

		if (cnt > p[i].x){

			long long xx = c[cnt], yy = c[p[i].x];

			ans += xx - yy;

		}

		int now = p[i].x + k;

		if (now > n) now = n;

		rep(j, max(cnt + 1, p[i].x + 1), now){

			for (auto u : v[j]){

				int cnt;

				int now = solve(p[i].x, p[u].x);

				if (p[i].y > now && p[u].y > now)

					cnt = p[i].y - now + p[u].y - now + abs(p[i].x - p[u].x);

				else cnt = abs(p[i].x - p[u].x) + abs(p[i].y - p[u].y);

				if (cnt <= k) ++ans;

			}

		}

	}

	printf("%lld\n", ans);

	return 0;

}

巴特西

计蒜客微软大楼设计方案（RMQ）

最新文章

热门文章

巴特西

计蒜客 微软大楼设计方案（RMQ）

最新文章

热门文章

计蒜客微软大楼设计方案（RMQ）