题目链接： 题意是说，有从 1 开始递增依次编号的很多球，开始他们都是黑色的，现在依次给出 n 个操作（ai，bi，ci），每个操作都是把编号 ai 到 bi 区间内的所有球涂成 ci 表示的颜色（黑 or 白），然后经过 n 次给定的操作后，求最长的连续白色区间的左端点和右端点。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <algorithm>
#include <set>
using namespace std;
typedef long long ll;
typedef unsigned long long Ull;
#define MM(a,b) memset(a,b,sizeof(a));
const double eps = 1e-10;
const int inf = 0x3f3f3f3f;
const double pi=acos(-1);
const int maxn=100000;
int cnt;
struct node{
ll l,r;
}ne[2*maxn+10];
bool cmp(node a,node b)
{
if(a.l!=b.l) return a.l<b.l;
else return a.r<b.r;
}
bool inter(node i,node j)
{
return j.r>=i.l&&j.l<=i.r;
}
void update(node &tmp,node &j)
{
if(tmp.l>j.l&&tmp.r<j.r)
{
ne[++cnt]=(node){tmp.r+1,j.r};
j=(node){j.l,tmp.l-1};
return;
}
if(tmp.l<=j.l&&tmp.r>=j.r)
{j.l=-1;j.r=-1;return;}
if(tmp.l>j.l)
j.r=tmp.l-1;
else j.l=tmp.r+1;
}
int main()
{
int n;
while(~scanf("%d",&n))
{
int l,r;
char op[5];
cnt=0;
for(int i=1;i<=n;i++)
{
scanf("%d %d",&l,&r);
if(l>r) swap(l,r);//题目只是说给定的范围
scanf("%s",op);
if(op[0]=='w')
{ne[++cnt].l=l;ne[cnt].r=r;}
else
{
node tmp=(node){l,r};
int curcnt=cnt;
for(int j=1;j<=curcnt;j++)
if(inter(tmp,ne[j]))
update(tmp,ne[j]);
}
}
sort(ne+1,ne+cnt+1,cmp);
node ans=(node){1,0};
for(int i=1;i<=cnt;)
{
node cur=(node){ne[i].l,ne[i].r};
if(cur.l<0) {i++;continue;}
while(cur.r+1>=ne[i].l)
{
cur.r=max(ne[i].r,cur.r);i++;//注意新加入的区间不///一定r大于当前
if(i>cnt) break;
}
if(cur.r-cur.l+1>ans.r-ans.l+1)
ans=cur;
}
if(ans.r!=0)
printf("%lld %lld
",ans.l,ans.r);
else printf("Oh, my god
");
}
return 0;
}
分析：最多int范围内的数的球，说明直接开数组是肯定不行的，考虑离散化，毕竟n<=2000,每个
节点代表一个区间，然后每次一出现一个新的黑色的节点，就考虑其对已经有的白色区间的干扰，最后
对所有的白色区间合并记录最长长度就好，参考文章；
wa代码：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <algorithm>
#include <set>
using namespace std;
typedef long long ll;
typedef unsigned long long Ull;
#define MM(a,b) memset(a,b,sizeof(a));
const double eps = 1e-10;
const int inf = 0x3f3f3f3f;
const double pi=acos(-1);
const int maxn=100000;
int cnt;
struct node{
ll l,r;
}ne[2*maxn+10];
bool cmp(node a,node b)
{
if(a.l!=b.l) return a.l<b.l;
else return a.r<b.r;
}
bool inter(node i,node j)
{
return j.r>=i.l&&j.l<=i.r;
}
void update(node &tmp,node &j)
{
if(tmp.l>j.l&&tmp.r<j.r)
{
j=(node){j.l,tmp.l-1};
ne[++cnt]=(node){tmp.r+1,tmp.r};
return;
}
if(tmp.l<=j.l&&tmp.r>=j.r)
{j.l=-1;j.r=-1;return;}
if(tmp.l>j.l)
j.r=tmp.l-1;
else j.l=tmp.r+1;
}
int main()
{
int n;
while(~scanf("%d",&n))
{
int l,r;
char op[5];
cnt=0;
for(int i=1;i<=n;i++)
{
scanf("%d %d",&l,&r);
scanf("%s",op);
if(op[0]=='w')
{ne[++cnt].l=l;ne[cnt].r=r;}
else
{
node tmp=(node){l,r};
for(int j=1;j<=cnt;j++)
if(inter(tmp,ne[j]))
update(tmp,ne[j]);
}
}
sort(ne+1,ne+cnt+1,cmp);
node ans=(node){0,0};
for(int i=1;i<=cnt;)
{
node cur=(node){ne[i].l,ne[i].r};
if(cur.l<0) continue;
while(inter(cur,ne[i]))
{cur.r=ne[i].r;i++;}
if(cur.r-cur.l+1>ans.r-ans.l+1)
ans=cur;
}
if(ans.l!=0&&ans.r!=0)
printf("%d %d
",ans.l,ans.r);
else printf("Oh, my god
");
}
return 0;
}