这题说的是给了 n 个操作。 每个操作会把 【a,b】 之间的球 涂为黑色或者 白色， 然后最后问 最长的连续的白色的 球有多少个，初始的时候全是黑的。
我们将所有的点离散化， 记得离散 a-1, b+1, 因为如果你不离散 a-1 那么 在区间间隔时 间隔是黑色的 没有操作的你会计算成白色的， 然后如果不加b+1 会使得同起点的区间白色的部分会被后来比他小的黑色区间覆盖， 导致最后 白色的少了
#include <iostream> #include <algorithm> #include <cstdio> #include <string.h> using namespace std; typedef long long ll; const int maxn = 4005; ll X[maxn],Y[maxn]; int op[maxn]; ll Loc[maxn*2]; int cL, cR ,V,tim; ll ansL,ansR,preL,preR; struct Itree{ int color[maxn*8]; void build(int o, int L, int R){ color[o]=2; } void pushdown(int o){ color[o*2]=color[o]; color[o*2+1]=color[o]; color[o]=-1; } void update(int o, int L , int R){ if(cL<=L && R<=cR ){ color[o]=V; return; } int mid=(L+R)/2; if(color[o]!=-1) pushdown(o); if(cL<=mid) update(o*2, L, mid); if(cR>mid) update(o*2+1, mid+1, R); } void endop(int o, int L, int R){ if(color[o]!=-1){ if(color[o]==1){ if(tim==0){ tim=1; preL=Loc[L-1]; preR=Loc[R-1]; if(preR-preL>ansR-ansL){ ansL=preL; ansR=preR; } }else{ preR=Loc[R-1]; if(preR-preL>ansR-ansL){ ansL=preL; ansR=preR; } } }else tim=0; return ; } if(L==R) return ; int mid=(L+R)/2; endop(o*2,L, mid); endop(o*2+1, mid+1,R); } }T; int main() { int n; char st[5]; while(scanf("%d",&n)==1){ int ge=0; for(int i=0; i<n; ++i ){ scanf("%I64d%I64d%s",&X[i],&Y[i],st); /* ll a = X[i] ,b =Y[i]; X[i]=min(a,b); Y[i]=max(a,b);*/ if(st[0]=='b') op[i]=2; else op[i]=1; Loc[ge++]=X[i]; Loc[ge++]=Y[i]; Loc[ge++]=X[i]-1; Loc[ge++]=Y[i]+1; } sort(Loc,Loc+ge); ge = unique(Loc,Loc+ge)-Loc; T.build(1,1,ge); for(int i=0; i<n; ++i){ cL =lower_bound(Loc,Loc+ge,X[i])-Loc+1; cR =lower_bound(Loc, Loc+ge, Y[i])-Loc+1; V=op[i]; T.update(1,1,ge); } ansL=1; ansR=-1;tim=0; T.endop(1,1,ge); if(ansL>ansR){ puts("Oh, my god"); }else{ printf("%I64d %I64d ",ansL, ansR); } } return 0; }