题目大意
题解
我国古代有一句俗话。
这句话在这道题上得到了鲜明的体现。
我的方法就是魔改版线段树，乱搞搞一下，首先借鉴了黄学长的建树方法，直接用一个节点维护年份的区间，但是这样就带来了问题，就是在查询的时候非常难以操作。经过不断的乱搞，我终于把正确的操作方式搞了出来。。。
另外这个题细节还是很多。详见胡泽聪dalao的分析
代码
#include <bits/stdc++.h>
using namespace std;
const int maxn = 50005;
struct seg {
int l, r, mx, know;
} t[maxn * 4];
int s[maxn], n, m;
void build(int k, int l, int r) {
if (l == r) {
scanf("%d %d", &t[k].l, &t[k].mx);
t[k].r = t[k].l;
t[k].know = 1;
return;
}
int mid = (l + r) >> 1;
build(k << 1, l, mid);
build(k << 1 | 1, mid + 1, r);
t[k].know = (t[k << 1].know && t[k << 1 | 1].know);
if (t[k << 1].r + 1 != t[k << 1 | 1].l)
t[k].know = 0;
t[k].l = t[k << 1].l;
t[k].r = t[k << 1 | 1].r;
t[k].mx = max(t[k << 1].mx, t[k << 1 | 1].mx);
}
int query_mx(int k, int x, int y) {
int l = t[k].l, r = t[k].r;
if (y < x)
return 0;
if (x < l)
x = l;
if (y > r)
y = r;
if (x == l && r == y)
return t[k].mx;
int mid = t[k << 1].r;
int nxmid = t[k << 1 | 1].l;
if (y < l || x > r)
return 0;
int ans = -0x3f3f3f;
if (x >= l && y < nxmid && x <= mid) {
ans = max(ans, query_mx(k << 1, x, y));
} else if (y <= r && x > mid && y >= nxmid) {
ans = max(ans, query_mx(k << 1 | 1, x, y));
} else if (x >= l && x <= mid && y >= nxmid && y <= r) {
ans = max(ans, query_mx(k << 1, x, mid));
ans = max(ans, query_mx(k << 1 | 1, nxmid, y));
} else
return 0;
return ans;
}
int query_know(int k, int x, int y) {
int l = t[k].l, r = t[k].r;
if (y < x)
return 0;
if (x < l || y > r)
return 0;
if (x == l && y == r)
return t[k].know;
else if (r - l == 0)
return 0;
bool ans = true;
int mid = t[k << 1].r;
int nxmid = t[k << 1 | 1].l;
if (x >= l && y < nxmid && x <= mid) {
ans = ans && query_know(k << 1, x, y);
} else if (y <= r && x > mid && y >= nxmid) {
ans = ans && query_know(k << 1 | 1, x, y);
} else if (x >= l && x <= mid && y >= nxmid && y <= r) {
ans = ans && query_know(k << 1, x, mid);
ans = ans && query_know(k << 1 | 1, nxmid, y);
ans = ans && (nxmid-mid <= 1) ? 1 : 0;
} else
return 0;
return ans;
}
int query(int k, int x) {
if (t[k].l == t[k].r)
return t[k].mx;
if (x <= t[k << 1].r)
return query(k << 1, x);
else if (x >= t[k << 1 | 1].l)
return query(k << 1 | 1, x);
else
return -1;
}
int main() {
//freopen("rain.in", "r", stdin);
//freopen("rain.ans", "w", stdout);
scanf("%d", &n);
build(1, 1, n);
scanf("%d", &m);
// cout << query_mx(1, 2003, 2007);
//cout << query_know(1, -138, -129) << endl;
// cout << query_know(1, 2004, 2006) << endl;
for (int i = 1; i <= m; i++) {
int x, y;
scanf("%d %d", &x, &y);
if (query_know(1, x, y) && (query(1, x) >= query(1, y)) &&
(query_mx(1, x + 1, y - 1) < query(1, y)))
printf("true\n");
else if (query_know(1, x, x) && query_know(1, y, y) &&
!(query_know(1, x + 1, y - 1)) &&
(query_mx(1, x + 1, y - 1) < query(1, y)) &&
(query(1, x) >= query(1, y)))
printf("maybe\n");
else if (query_know(1, x, x) && !(query_know(1, y, y)) && (query_mx(1,x+1,y-1) < query(1,x)))
printf("maybe\n");
else if (query_know(1, y, y) && !(query_know(1, x, x)) &&
(query_mx(1, x + 1, y - 1) < query(1, y)))
printf("maybe\n");
else if ((!(query_know(1, x, x)) && (!(query_know(1, y, y)))))
printf("maybe\n");
else
printf("false\n");
}
return 0;
}
Ps.开始对着样例乱搞出的代码居然得了50分