线段树50pts求调
查看原帖
线段树50pts求调
754310
Pepsee楼主2023/9/20 17:32
#include <bits/stdc++.h>
#define lson k<<1
#define rson k<<1|1
#define int long long
using namespace std;
int n,q;
int Y[114514],v[114514];
struct t{
	int mx,l,r;
}tr[4*114514];
int max(int a,int b){
	return a>b?a:b;
}
void update(int k){
	tr[k].mx = max(tr[lson].mx,tr[rson].mx);
}
void build(int l,int r,int k)
{
	tr[k].l = l; tr[k].r = r;
	if (l == r){
		tr[k].mx = v[l];
		return ;
	}
	int mid = (l+r) >> 1;
	build(l,mid,lson);
	build(mid+1,r,rson);
	update(k);
}
int sum = 0;
void find(int k,int x,int y)
{
	if (x <= tr[k].l && tr[k].r <= y)
	{
		sum = max(sum,tr[k].mx);
		return ;
	}
	int mid = (tr[k].l+tr[k].r) >> 1;
	if (x <= mid) find(lson,x,y);
	if (y > mid) find(rson,x,y);
}
signed main()
{
	scanf("%lld",&n);
	for (int i = 1; i <= n; i++)
		scanf("%lld %lld",&Y[i],&v[i]);
	build(1,n,1);
	scanf("%lld",&q);
	while (q--)
	{
		int x,y;
		sum = 0;
		scanf("%lld %lld",&x,&y);
		if (x >= y){
			printf("false\n");
			continue;
		}
		int l = lower_bound(Y+1,Y+n+1,x)-Y,r = lower_bound(Y+1,Y+n+1,y)-Y;
		int flag1 = (Y[l]==x),flag2 = (Y[r]==y);
		if (!flag1) l--;
		find(1,l+1,r-1);
		if ((sum >= v[r]&&flag2) || (v[l]<v[r]&&flag1&&flag2) || (sum>=v[r]&&flag1))
			printf("false\n");
		else if (r-l!=Y[r]-Y[l] || !flag1 || !flag2)
			printf("maybe\n");
		else printf("true\n");
	}
	return 0;
}
2023/9/20 17:32
加载中...