萌新求助
查看原帖
萌新求助
213699
MistZero楼主2020/5/6 21:26

照着同学的代码打的,求助!

#include <bits/stdc++.h>
using namespace std;

const int N = 5e4 + 10;

int st[N][100];
int n, m, x;

map <int, int> id;

inline void input (int &ret) {
	ret = 0; char ch = getchar ();
	while (!isdigit (ch)) ch = getchar ();
	while (isdigit (ch)) {
		ret = (ret << 1) + (ret << 3) + (ch ^ '0');
		ch = getchar ();
	}
}

inline void buildstable () {
	for (register int i = 1; (1 << i) <= n; ++ i) {
		for (register int j = 1; j + (1 << i) - 1 <= n; ++ j) {
			st[j][i] = max (st[j][i - 1], st[j + (1 << (i - 1))][i - 1]);
		}
	}
	return;
}

inline int query (int l, int r) {
	int Pos = 0;
	while (1 << (Pos + 1) <= (r - l + 1)) ++ Pos;
	return max (st[l][Pos], st[r - (1 << Pos) + 1][Pos]);
}

int main () {
	input (n);
	for (register int i = 1; i <= n; ++ i) {
		input (x); input (st[i][0]);
		id[x] = i;
	}
	buildstable ();
	input (m);
	while (m --) {
		int l, r;
		input (r); input (l);
		if (r >= l) {
			puts ("false");
			continue;
		} // 直接无解输出 false
		bool flagl = id.count (l);
		bool flagr = id.count (r);
		bool flag = false;
		if (!flagl && !flagr) {
			puts ("maybe");
			continue;
		} // 没有提到过直接输出 false
		map <int, int> :: iterator mapl;
		map <int, int> :: iterator mapr;
		int left, right;
		mapl = id.lower_bound (l);
		mapr = id.lower_bound (r);
		if (mapl == id.end ()) {
			puts ("maybe");
			continue;
		} // 有一个未知
		left = (mapl == id.end ()) ? id.size () + 1 : mapl -> second;
		right = mapr -> second;
		if (!flagr) -- right;
		int _left = (right + 1 <= left - 1) ? query (right + 1, left - 1) : 0;
		if (!flagr) flag = (_left < st[left][0]);
		else if (!flagl) flag = (st[right][0] > _left);
		else flag = (st[right][0] >= st[left][0] && st[left][0] > _left);
		if (flagl && flagr && (right - left) == (r - l)) {
			if (flag) puts ("true");
			else puts ("false"); // 均已知但是区间内有未知
		} else {
			if (flag) puts ("maybe");
			else puts ("false");
		} // 整个区间都已知
	}
	return 0;
}
2020/5/6 21:26
加载中...