70,求助
查看原帖
70,求助
660776
ananran998楼主2023/4/27 00:39
#include <bits/stdc++.h>
using namespace std;

int n, q, f[200001], ye[50001], re[50001];
map<int, int> mp;

inline void buildtree(int k, int l, int r) {
	if (l == r) {
		f[k] = re[l];
		return;
	}
	int m = (l + r) / 2;
	buildtree(k + k,  l, m);
	buildtree(k + k + 1, m + 1, r);
	f[k] = max(f[k + k], f[k + k + 1]);
}

int calc(int k, int l, int r,int x, int y) {
	if (l == x && r == y) 
		return f[k];
	int m = (l + r) / 2;
	if (y <= m)
		return calc(k + k, l, m, x, y);
	else if (x > m)
		return calc(k + k + 1, m + 1, r, x, y);
	else
		return max(calc(k + k, l, m, x, m), calc(k + k + 1, m + 1, r, m + 1, y));
}

inline void print(int ok, int y2, int y1, int y, int x) {
	if (!ok)
		printf("false\n");
	else {
		if (y2 - y1 == y - x)
			printf("true\n");
		else
			printf("maybe\n");
	}
}

int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) {
		scanf("%d%d", &ye[i], &re[i]);
		mp[ye[i]] = i;
	}
	buildtree(1, 1, n);
	scanf("%d", &q);
	while (q--) {
		int y1, y2;
		scanf("%d%d", &y1, &y2);
		if (y1 > y2) {
			printf("false\n");
			continue;
		}
		int x = mp[y1], y = mp[y2];
		if (x == 0)
			x = lower_bound(ye + 1, ye + n + 1, y1) - ye;
		if (y == 0)
			y = lower_bound(ye + 1, ye + n + 1, y2) - ye;
		bool f1 = ye[x] == y1, f2 = ye[y] == y2;
		if (f1 && !f2) {
			int ok = 1;
			if (x + 1 <= y - 1) {
				int mx = calc(1, 1, n, x + 1, y - 1);
				if (mx >= re[x])
					ok = 0;
			}
			print(ok, y2, y1, y, x);
		} else if (!f1 && f2) {
			int ok = 1;
			if (x <= y - 1) {
				int mx = calc(1, 1, n, x, y - 1);
				if (mx >= re[y])
					ok = 0;
			}
			print(ok, y2, y1, y, x);
		} else if (!f1 && !f2)
			printf("maybe\n");
		else {
			int ok = 1;
			if (re[x] < re[y])
				ok = 0;
			if (ok && x + 1 <= y - 1) {
				int mx = calc(1, 1, n, x + 1, y - 1);
				if (mx >= re[y])
					ok = 0;
			}
			print(ok, y2, y1, y, x);
		}
	}
	return 0;
}
2023/4/27 00:39
加载中...