题解 P2471 【[SCOI2007]降雨量】
FC_Viiiiictor_K · · 题解
翻了一圈没看见动态开点线段树，于是给动态开点线段树信仰玩家贡献一篇题解
众所周知动态开点线段树可以维护更广阔的值域，但是年份有可能有负数，于是我们直接暴力给每一个年份加一个大小为1e9+9的常量shift，把负数平移成正数，然后把值域开两倍；
然后就是维护区间最大值、最小值、连续性，各种特判即可，其他题解中已经讲得很清楚了。
需要注意的是，在我的写法中，询问的x和y是反的，而且区间查询涉及到[x+1,y-1]这个区间，所以还要多特判一下x紧挨着y的情况，防止区间查询出锅。
#define INL inline
#define REG register
#define M (int)(((long long)l+r)>>1)
#define LS tre[pos].lson
#define RS tre[pos].rson//动态开点线段树需要的宏定义
#include <cstdio>
#include <iostream>
using namespace std;
INL int read(){
REG int sum=0,sign=1;
REG char tmp=getchar();
while(tmp<'0'||tmp>'9'){
if(tmp=='-'){
sign=-1;
}
tmp=getchar();
}
while(tmp>='0'&&tmp<='9'){
sum=(sum<<1)+(sum<<3)+(tmp-'0');
tmp=getchar();
}
return sum*sign;
}//快读
const int maxn=114514,shift=1e9+9/*就是这个常量把负数年份变成了正数*/;
int n,m;
struct node{
int lson,rson,maxv,minv;//左儿子，右儿子，区间最大、最小
bool sure;//区间连续性，连续为1，不连续为0
}tre[maxn<<6];
int cntr=2;
INL void insert(REG int tar,REG int x){
REG int l=1,r=shift<<1,pos=1;
while(l!=r){//普通线段树单点操作的非递归写法
//cout<<l<<' '<<r<<endl;
tre[pos].maxv=max<int>(tre[pos].maxv,x);
tre[pos].minv=min<int>(tre[pos].minv,x);
tre[pos].sure=1;
if(tar<=M){
if(!LS){
LS=cntr++;//动态开点
}
r=M;
tre[pos].sure&=tre[RS].sure;//我写题解的时候才发现我不确定这样维护区间连续性是不是对的，反正是过了，大家老老实实的递归写上推就好
pos=LS;
}
else{
if(!RS){
RS=cntr++;//还是动态开点
}
l=M+1;
tre[pos].sure&=tre[LS].sure;
pos=RS;
}
}
tre[pos].maxv=tre[pos].minv=x;
tre[pos].sure=1;
}
INL int query(REG int tar){//单点查询值
REG int l=1,r=shift<<1,pos=1;
while(l!=r){
if(tar<=M){
r=M;
pos=LS;
}
else{
l=M+1;
pos=RS;
}
}
return tre[pos].maxv;
}
INL bool check(REG int al,REG int ar,REG int x,REG int l,REG int r,REG int pos){//询问区间最大值是否小于某数
if(!pos){
return 1;//不确定的情况默认为可行
}
if(al<=l&&ar>=r){
return tre[pos].maxv<x;
}
REG bool able=1;
if(al<=M){
able&=check(al,ar,x,l,M,LS);
}
if(ar>M){
able&=check(al,ar,x,M+1,r,RS);
}
return able;
}
INL bool rcheck(REG int al,REG int ar,REG int x,REG int l,REG int r,REG int pos){//询问区间最小值是否大于某数
if(!pos){
return 1;//同上个函数
}
if(al<=l&&ar>=r){
return tre[pos].minv>x;
}
REG bool able=1;
if(al<=M){
able&=check(al,ar,x,l,M,LS);
}
if(ar>M){
able&=check(al,ar,x,M+1,r,RS);
}
return able;
}
INL bool getsure(REG int al,REG int ar,REG int l,REG int r,REG int pos){//查询区间连续性
if(al<=l&&ar>=r){
return tre[pos].sure;
}
REG bool ans=1;
if(al<=M){
ans&=getsure(al,ar,l,M,LS);
}
if(ar>M){
ans&=getsure(al,ar,M+1,r,RS);
}
return ans;
}
int main(){
freopen("SCOI2007D1T2.in","r",stdin);
n=read();
for(REG int i=0;i<n;i++){
REG int key=read()+shift/*把可能为负的年份移到必定正数*/,val=read();
insert(key,val);
}
m=read();
for(REG int i=0;i<m;i++){
REG int x=read()+shift,y=read()+shift;
REG int linex=query(x),liney=query(y);
if(x>=y){
printf("false\n");
continue;
}
else if(x==y-1){//关于x紧挨y的特判
if(linex&&liney){
if(linex>=liney){
printf("true\n");
}
else{
printf("false\n");
}
}
else{
printf("maybe\n");
}
continue;
}
if(linex&&liney){//往下就是各种特判了，写的贼乱
if(linex>=liney&&check(x+1,y-1,liney,1,shift<<1,1)){
if(getsure(x+1,y-1,1,shift<<1,1)){
printf("true\n");
}
else{
printf("maybe\n");
}
}
else{
printf("false\n");
}
}
else if(linex){
if(rcheck(x+1,y-1,linex,1,shift<<1,1)){
printf("maybe\n");
}
else{
printf("false\n");
}
}
else if(liney){
if(check(x+1,y-1,liney,1,shift<<1,1)){
printf("maybe\n");
}
else{
printf("false\n");
}
}
else{
printf("maybe\n");
}
}
return 0;
}