来自"NOCOW"

这题要离散化，离散化点，但是把离散化之后的东西看做是一个左闭右开的区间，具体见程序。

By WinterLegend

program         p1019 ;
type    segtype = record a , b : longint ; w : boolean end ;
        ptype   = record v , id : longint ; f : boolean end ;
var     s       : array[0..5010] of segtype ;
        p       : array[0..10010] of ptype ;
        hash    : array[0..10010] of longint ;
        axis    : array[0..10010] of boolean ;
        n       : longint ;
 
procedure       qsort (s , t : longint) ;
var     i , j , key
                : longint ;
        d       : ptype ;
begin
        i := s ; j := t ; key := p[s + random (t-s+1)].v ;
        repeat
         while (p[i].v < key) do inc (i) ;
         while (p[j].v > key) do dec (j) ;
         if (i <= j) then begin
          d := p[i] ; p[i] := p[j] ; p[j] := d ;
          inc (i) ; dec (j) ;
         end ;
        until (i > j) ;
        if (s < j) then qsort (s , j) ;
        if (i < t) then qsort (i , t) ;
end ;
 
procedure       solve ;
var     i , j , t1 , t2 , ans , la , cnt
                : longint ;
        c       : char ;
        p0      : boolean ;
begin
        readln (n) ;
        for i := 1 to n do begin
         readln (s[i].a , s[i].b , c , c) ;
         if (c = 'w') then s[i].w := false else s[i].w := true ;
         p[(i shl 1)-1].v := s[i].a ;
         p[(i shl 1)-1].id := i ;
         p[(i shl 1)-1].f := false ;
         p[i shl 1].v := s[i].b ;
         p[i shl 1].id := i ;
         p[i shl 1].f := true ;
        end ;
 
        qsort (1 , 2 * n) ;
        cnt := 0 ; la := -1 ;
        for i := 1 to 2 * n do begin
         if (p[i].v <> la) then begin
          inc (cnt) ; hash[cnt] := p[i].v ; la := p[i].v ;
         end ;
         if (not p[i].f) then
          s[p[i].id].a := cnt
         else
          s[p[i].id].b := cnt ;
        end ;
 
        for i := 1 to n do
         for j := s[i].a to s[i].b - 1 do
          axis[j] := s[i].w ;
 
        hash[0] := 0 ; axis[0] := false ;
        hash[2*n+1] := 1000000000 ; axis[2*n+1] := true ;
        ans := 0 ; p0 := axis[0] ; la := hash[0] ;
        for i := 1 to 2 * n + 1 do
         if (axis[i] <> p0) then
          if (not p0) then begin
           if (hash[i] - hash[la] > ans) then begin
            ans := hash[i] - hash[la] ;
            t1 := hash[la] ; t2 := hash[i] ;
           end ;
           p0 := true ; la := i ;
          end
          else begin
           p0 := false ; la := i ;
          end ;
 
        writeln (t1,' ',t2) ;
end ;
 
begin
        assign (input , 'p1019.in') ; reset (input) ;
        assign (output , 'p1019.out') ; rewrite (output) ;
 
        randomize ;
        solve ;
 
        close (input) ; close (output) ;
end .

看到这道题马上想到离散化，当然也有不离散化的方法，如倒序染色，但是这道题还是用离散化更方便。离散化后就随便怎么做了，线段树可以，朴素可以，什么都可以。我是用朴素。

program cao;
const
  bigprime=48889;
  maxn=10100;
 
type
  color=(black,white);
 
var
  t,f:array[0..bigprime] of longint;
  axis,kind:array[0..maxn] of color;
  data,left,right:array[0..maxn] of longint;
  a,b,i,j,k,l,n,m,p,q,total,ans1,ans2,tmp:longint;
  ch:char;
 
function hash(a:longint):longint;
var
  i:longint;
begin
  i:=a mod bigprime;
  while (t[i]<>-1)and(t[i]<>a) do i:=(i+1) mod bigprime;
  if t[i]=-1 then begin inc(total); t[i]:=a; f[i]:=total end;
  exit(f[i]);
end;
 
procedure swap(var a,b:longint);
begin
  tmp:=a;
  a:=b;
  b:=tmp;
end;
 
procedure qsort(left,right:longint);
var
  i,j,x:longint;
begin
  i:=left;
  j:=right;
  x:=data[(i+j) shr 1];
  while i<j data[j] while inc(i); do data[i]><x begin>x do dec(j);
    if i<=j then
    begin
      swap(data[i],data[j]);
      inc(i);
      dec(j);
    end;
  end;
  if i<right j if qsort(i,right); then>left then qsort(left,j);
end;
 
procedure init;
begin
  readln(n);
  for i:=1 to n do
  begin
    readln(left[i],right[i],ch,ch);
    if ch=‘w’ then kind[i]:=white else kind[i]:=black;
    data[i shl 1]:=left[i];
    data[(i shl 1)-1]:=right[i];
  end;
  data[(n shl 1)+1]:=0;
  data[(n shl 1)+2]:=1000000000;
  total:=0;
  fillchar(t,sizeof(t),255);
  for i:=0 to maxn do
    axis[i]:=white;
end;
 
procedure main;
begin
  qsort(1,(n shl 1)+2);
  for i:=1 to (n shl 1)+2 do
    hash(data[i]);
  k:=hash(43);
  for i:=1 to n do
    for j:=hash(left[i]) to hash(right[i])-1 do
      axis[j]:=kind[i];
end;
 
procedure print;
begin
  k:=0;
  j:=0;
  for i:=1 to (n shl 1)+1 do
  begin
    if axis[hash(data[i])]=white then
    begin
      inc(j,data[i+1]-data[i]);
      b:=data[i+1];
    end
    else
    begin
      if k<j then
      begin
        k:=j;
        ans1:=a;
        ans2:=b;
      end;
      j:=0;
      a:=data[i+1];
    end;
  end;
  if k<j then
  begin
    k:=j;
    ans1:=a;
    ans2:=b;
  end;
  writeln(ans1,‘ ‘,ans2);
end;
 
begin
  init;
  main;
  print;
end.

贴上我的C++程序，供大家参考。此题只需离散化+朴素。

//By JackDavid127
#include <iostream>
using namespace std;
int pat(int r[],int i,int j){
	int p=r[i];
	while (i<j){
		while (i<j&&r[j]>=p) j--;
		if(i<j) r[i++]=r[j];
		while (i<j&&r[i]<=p) i++;
		if(i<j) r[j--]=r[i];
	}
	r[i]=p;
	return i;
}
void qsort(int r[],int low,int high){
	if(low<high){
		int p=pat(r,low,high);
		qsort(r,low,p-1);
		qsort(r,p+1,high);
	}
}
int n,num[10001];
bool flag[10001]={0};
struct node{
	int l,r;
	bool f;
}nodes[5001];
int main(){
	cin>>n;
	int i,j,a,b,m=0,x,y;
	char c;
	for (i=0;i<n;i++){
		cin>>a>>b>>c;
		nodes[i].l=a;
		for (j=0;j<m;j++) if(num[j]==a) break;
		if(j==m) num[m++]=a;
		nodes[i].r=b;
		for (j=0;j<m;j++) if(num[j]==b) break;
		if(j==m) num[m++]=b;
		nodes[i].f=(c=='b')?1:0;
	}
	for (j=0;j<m;j++) if(num[j]==1000000000) break;
	if(j==m) num[m++]=1000000000;
	for (j=0;j<m;j++) if(num[j]==0) break;
	if(j==m) num[m++]=0;
	qsort(num,0,m-1);
	/*
	for (i=0;i<m;i++) cout<<num[i]<<' ';
	cout<<endl;
	*/
	for (i=0;i<n;i++){
		for (j=0;j<m-1&&nodes[i].r>=num[j+1];j++)
			if(nodes[i].l<=num[j]&&nodes[i].r>=num[j+1]) flag[j]=nodes[i].f;
		/*
		for (j=0;j<m-1;j++) cout<<((flag[j])?'b':'w')<<' ';
		cout<<endl;
		*/
	}
	i=0;
	x=0;y=-1;
	while (i<m-1){
		if(flag[i]) {i++;continue;}
		j=i+1;
		while (j<m-1&&!flag[j]) j++;
		if(num[j]-num[i]>y-x) {y=num[j];x=num[i];}
		i=j;
	}
	cout<<x<<' '<<y;
	return 0;
}

by zhujf553 注意区间的开闭，被这纠结了。。。

#include <iostream>
#include <stdlib.h>
#include <string>
 
using namespace std;
 
const int maxn = 5002;
 
struct Cda
{
	Cda(){};
	Cda(int _x, int _k, int _i):x(_x), k(_k), i(_i){};
	int x, k, i;
};
 
Cda d[maxn * 2];
 
int n, tot;
string sign[maxn];
int smap[maxn * 2];
int ss[maxn][2];
bool v[maxn * 2];
 
void init()
{
	cin >> n;
	n++;
	d[1] = Cda(0, 0, 1);
	d[2] = Cda(1000000000, 1, 1);
	sign[1] = "w";
	for(int i = 2 ; i <= n ; i++)
	{
		int x, y;
		cin >> x >> y >> sign[i];
		d[i * 2 - 1] = Cda(x, 0, i);
		d[i * 2] = Cda(y, 1, i);
	}
}
 
int cmp(const void *A, const void *B)
{
	Cda *a = (Cda *)A, *b = (Cda *)B;
	return a -> x - b -> x;
}
 
void work()
{
	qsort(d + 1, n * 2, sizeof(Cda), cmp);
	for(int i = 1 ; i <= n * 2 ; i++)
	{
		if(i == 1 || d[i].x != d[i - 1].x)
		{
			tot++;
			smap[tot] = d[i].x;
		}
		ss[d[i].i][d[i].k] = tot;
	}
	for(int i = 1 ; i <= n ; i++)
	{
		bool tmp = sign[i] == "b";
		for(int j = ss[i][0] + 1 ; j <= ss[i][1] ; j++)
			v[j] = tmp;
	}
	int k = 0, ma = 0, m1, m2;
	v[tot + 1] = true;
	for(int i = 1 ; i <= tot + 1 ; i++)
	{
		if(!v[i])
		{
			k += smap[i] - smap[i - 1];
		}
		else 
		{
			if(k > ma) ma = k, m1 = smap[i - 1];
			k = 0;
		}
	}
	cout << m1 - ma << ' ' << m1 << endl;
}
 
int main()
{
	init();
	work();
	return 0;
}