RE求调!
查看原帖
RE求调!
1128039
ybc2026lhy楼主2024/7/12 17:19
#include <bits/stdc++.h>
using namespace std;
const int N = 5e5 + 5;
#define int long long
#define lc(i) ((i)*2)
#define rc(i) ((i)*2 + 1)
struct node {
	int l, r;
	int maxdat;
} tree[4 * N];
struct jyl{
	int num,val=INT_MIN;
}a[N];
int n, m,cnt=0;
void build(int p, int l, int r) {
	tree[p].l = l, tree[p].r = r;
	if (l == r) {
		tree[p].maxdat = a[l].val;
		return;
	}
	int mid = (l + r) / 2;
	cnt++;
	build(lc(p), l, mid);
	build(rc(p), mid + 1, r);
	tree[p].maxdat = max(tree[lc(p)].maxdat, tree[rc(p)].maxdat);
}
int query(int p, int l, int r) {
	if (tree[p].l >= l && tree[p].r <= r)
		return tree[p].maxdat;
	int mid = (tree[p].l + tree[p].r) / 2;
	int val = -(1 << 30);
	if (l <= mid)
		val = max(val, query(lc(p), l, r));
	if (r > mid)
		val = max(val, query(rc(p), l, r));
	return val;
}
signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> a[i].num>>a[i].val;
	}
	build(1, a[1].num, a[n].num);
	cin >> m;
	for (int i = 1; i <= m; i++) {
		int l, r;
		cin >> l >> r;
		if(l>=r){
			cout<<"false"<<"\n";
		} else if(a[l].val==INT_MIN&&a[r].val==INT_MIN){
			cout<<"maybe"<<"\n";
		} else if(a[l].val==INT_MIN){
			if(query(1,l+1,r-1)>=a[r].val){
				cout<<"false"<<"\n";
			} else {
				cout<<"maybe"<<"\n";
			}
		} else if(a[r].val==INT_MIN){
			cout<<"maybe"<<"\n";
		} else if(cnt==r-l+1){
			if(query(1,l+1,r-1)>=a[r].val){
				cout<<"false"<<"\n";
			} else {
				cout<<"true"<<"\n";
			}
		} else {
			if(query(1,l+1,r-1)>=a[r].val){
				cout<<"false"<<"\n";
			} else {
				cout<<"true"<<"\n";
			}
		}
	}
}
2024/7/12 17:19
加载中...