本文共 1432 字，大约阅读时间需要 4 分钟。
细节挺多的，下午脑子还算机敏
大体分四类，讨论左右端点是否存在。怎么和平衡树删除这么像
1.都不存在，肯定是maybe
2.左端点不存在，判断中间一段的最大值和右端点的关系
3.右端点不存在，判断中间一段的最大值和左端点的关系（这里有点疑惑，感觉自己写错了，居然过了）
4.都存在，先判断端点大小，再判断中间最大值（即使等于右端点也不行），再判断有没有空下的（maybe）
分类讨论。
#include #include #include #include #include #define MAYBE puts("maybe"),0#define TRUE puts("true"),0#define FALSE puts("false"),0using namespace std;const int MAXN=100005;inline int rd(){ int ret=0,f=1;char c; while(c=getchar(),!isdigit(c))f=c=='-'?-1:1; while(isdigit(c))ret=ret*10+c-'0',c=getchar(); return ret*f;}int n,m;int year[MAXN];int f[MAXN][32],val[MAXN];map M;int query(int x,int y){ if(x==y) return f[x][0]; if(x>y) return -(1<<30); int len=log2(y-x+1); return max(f[x][len],f[y-(1< =val[posy]) return FALSE; else return MAYBE; } if(!M.count(y)){ posx=M[x];posy=lower_bound(year+1,year+1+n,y)-year; int mx=query(posx+1,posy-1); if(mx>=val[posx]) return FALSE;//? else return MAYBE; } posx=M[x];posy=M[y]; if(val[posy]>=val[posx]) return FALSE; int mx=query(posx+1,posy-1);// if(mx>=val[posy]) return FALSE;// if(posy-posx!=y-x) return MAYBE; return TRUE;}int main(){ n=rd(); for(int i=1;i<=n;i++){ M[year[i]=rd()]=i;f[i][0]=val[i]=rd(); } for(int j=1;(1< <=n;j++) for(int i=1;i<=n;i++) f[i][j]=max(f[i][j-1],f[i+(1<<(j-1))][j-1]); m=rd(); while(m--) solve(); return 0;}
转载于:https://www.cnblogs.com/ghostcai/p/9263599.html