P7145 降雨量 求条

常规
,
1 
// 思路来源：https://www.luogu.com.cn/article/1j5aktch
#include <algorithm>
#include <cstdio>

const int N = 5e4 + 5, LGN = 20;
int n, m, x, y, u, v, year[N], val[N], a[N][LGN];

int query(int l, int r);

int main(void)
{
	scanf("%d", &n);
	
	for (int i = 1; i <= n; i++)
	{
		scanf("%d %d", &year[i], &val[i]);
		a[i][0] = val[i];
	}
	
	for (int j = 1; j <= 31 - __builtin_clz(n); j++) 
	{
	    for (int i = 1; i <= n; i++) 
	    {
	        a[i][j] = std::max(a[i][j - 1], a[i + (1 << (j - 1))][j - 1]);
		}
	}
	
	scanf("%d", &m);
	
	for (int i = 1; i <= m; i++)
	{
		scanf("%d %d", &x, &y);
		
		u = std::lower_bound(year + 1, year + 1 + n, y) - year;
		v = std::lower_bound(year + 1, year + 1 + n, x) - year;

		if (u != n + 1 && year[u] == x && v != n + 1 && year[v] == y) // 左右端点都存在
		{
			if (val[u] < val[y]) // 懂得都懂
			{
				printf("false\n");
				
				continue;
			}
			
			if (v == u + 1)
			{
				if (x == y + 1)
				{
					printf("true\n");
				}
				else
				{
					printf("maybe\n");
				}
				
				continue;
			}
			
			if (query(u + 1, v - 1) >= val[v])
			{
				printf("false\n");
				
				continue;
			}
			
			if (x - y == v - u)
			{
				printf("true\n");
				
				continue;
			}
			else
			{
				printf("maybe\n");
				
				continue;
			}
		}
		else if (u != n + 1 && year[u] == x && (v == n + 1 || year[v] != y))
		{
			if (u == v)
			{
				printf("maybe\n");
				
				continue;
			}
			
			if (query(u, v - 1) >= val[v])
			{
				printf("false\n");
				
				continue;
			}
			else
			{
				printf("maybe\n");
				
				continue;
			}
		}
		else if ((u == n + 1 && year[u] != x) && v != n + 1 && year[v] == y)
		{
			if (v == u + 1)
			{
				printf("maybe\n");
				
				continue;
			}
			
			if (query(u, v - 1) >= val[u])
			{
				printf("false\n");
				
				continue;
			}
			else
			{
				printf("maybe\n");
				
				continue;
			}
		}
		else
		{
			printf("maybe\n");
		}
	}
	
	return 0;
}

int query(int l, int r)
{
	return std::max(a[l][31 - __builtin_clz(r - l + 1)], a[r - (1 << (31 - __builtin_clz(r - l + 1))) + 1][31 - __builtin_clz(r - l + 1)]);
}
2 
if(右端点不存在){
    if(左端点不存||降雨量比最大值要大) cout<<"maybe"<<endl;
    else cout<<"false"<<endl;
}else if(左端点存在){
    if(右端点比左端点大||右端点不是最大值) cout<<"false"<<endl;
    else if(所有年份已知) cout<<"true"<<endl;
    else cout<<"maybe"<<endl;
}else{
    if(右端点不是最大值) cout<<"false"<<endl;
    else cout<<"maybe"<<endl;
}
//最大值用倍增求，找左右端点用二分

qwq