这道题的大题思路就是模拟
假设给定的年份是x,y,首先分为4个大的情况,分别是
x的信息已知,y的信息已知
x的信息已知,y的信息未知
x的信息未知,y的情况已知
x的信息未知,y的情况未知
然后对于每一种情况可以根据x到y区间是否存在空位,最大值是否唯一,以及x,y,区间最大值的关系来判定。
所以对于区间的问题的合并与处理我们用线段树来存就行了。
反思:开始对情况的优先级判断不清,没有整理好思路就开始写。最后发现线段树的合并函数写错了。
/************************************************************** Problem: 1067 User: BLADEVIL Language: Pascal Result: Accepted Time:580 ms Memory:5304 kb ****************************************************************/ //By BLADEVIL type rec =record left, right :longint; max :longint; flag, flag2 :boolean; pred, succ :longint; end; var n, m :longint; a, b :array[0..50010] of longint; t :array[0..200010] of rec; function getmax(a,b:longint):longint; begin if a>b then exit(a) else exit(b); end; function combine(a,b:rec):rec; begin with combine do begin max:=getmax(a.max,b.max); pred:=a.pred; succ:=b.succ; if a.succ=b.pred-1 then flag:=true else flag:=false; flag:=flag and a.flag and b.flag; if a.max=b.max then flag2:=false else flag2:=true; if max=a.max then flag2:=flag2 and a.flag2; if max=b.max then flag2:=flag2 and b.flag2; left:=a.left; right:=b.right; end; end; procedure build(x,l,r:longint); var mid :longint; begin t[x].left:=l; t[x].right:=r; if l=r then begin with t[x] do begin pred:=a[l]; succ:=a[l]; flag2:=true; max:=b[l]; flag:=true; end; exit; end; with t[x] do mid:=(left+right)>>1; build(x<<1,l,mid); build(x<<1+1,mid+1,r); t[x]:=combine(t[x<<1],t[x<<1+1]); end; procedure init; var i :longint; begin read(n); for i:=1 to n do read(a[i],b[i]); a[0]:=-1; build(1,1,n); end; function getadress(x:longint):longint; var l, r, mid :longint; ans :longint; begin l:=1; r:=n; ans:=0; while l<=r do begin mid:=(l+r)>>1; if a[mid]<=x then begin ans:=mid; l:=mid+1; end else r:=mid-1; end; exit(ans); end; function ask(x,l,r:longint):rec; var mid :longint; begin if (t[x].left=l) and (t[x].right=r) then exit(t[x]); with t[x] do mid:=(left+right)>>1; if mid<l then exit(ask(x<<1+1,l,r)) else if mid>=r then exit(ask(x<<1,l,r)) else exit(combine(ask(x<<1,l,mid),ask(x<<1+1,mid+1,r))); end; procedure main; var i :longint; x, y :longint; u, v :longint; query :rec; begin read(m); for i:=1 to m do begin read(x,y); if x>y then begin writeln(‘false‘); continue; end; if x=y then begin writeln(‘true‘); continue; end; u:=getadress(x); v:=getadress(y); if (a[u]=x) and (a[v]=y) then begin if b[v]>b[u] then begin writeln(‘false‘); continue; end; query:=ask(1,u+1,v); if not query.flag2 then begin writeln(‘false‘); continue; end; if query.max<>b[v] then begin writeln(‘false‘); continue; end; query:=ask(1,u,v); if not query.flag then begin writeln(‘maybe‘); continue; end else begin writeln(‘true‘); continue; end; end else if (a[u]<>x) and (a[v]<>y) then begin writeln(‘maybe‘); continue; end else if (a[u]=x) and (a[v]<>y) then begin if u=v then begin writeln(‘maybe‘); continue; end; query:=ask(1,u+1,v); if query.max>=b[u] then begin writeln(‘false‘); continue; end else begin writeln(‘maybe‘); continue; end; end else if (a[u]<>x) and (a[v]=y) then begin if u=v then begin writeln(‘maybe‘); continue; end; query:=ask(1,u+1,v); if not query.flag2 then begin writeln(‘false‘); continue; end; if query.max<>b[v] then begin writeln(‘false‘); continue; end else begin writeln(‘maybe‘); continue; end; end; end; end; begin init; main; end.