题意：一开始全部点为黑色，然后给n个区间染色，染色为白色或黑色，最后统计哪段区间白色最长，要最右边的。
这题因为没说区间有多少个点，所以一开始不知道线段树要维护多长的区间，但是操作只有2000种，所以离散化之后点数也就4000，但是如果本来不连续的区间，离散化后可能就连续了，为了解决这个，要在把L-1,R+1也加到离散化数组里总共8000个点，然后L~R之间的线段是跟着L~R这个区间一起染色的，所以不必再（L，R）中找个点表示两点之间的线段的状态，然后为了求区间的最长连续1的起点和终点，每个节点都要维护最长连续1的最小起终点lnod,rnod,左端点颜色lcol,左端点连续1个数lnum，右端点颜色rcol,右端点连续1个数rnum，lnod，rnod维护的是真实值，lnum和rnum维护的是离散值，最后以后update，query函数能剪枝就要剪枝，递归太深段错误
#include<bits/stdc++.h>
using namespace std;
#define ls rt<<1
#define rs (rt<<1)+1
#define ll long long
#define fuck(x) cout<<#x<<" "<<x<<endl;
#pragma comment(linker, "/STACK:102400000,102400000")
const int maxn=10000+10;
int d[4][2]={1,0,-1,0,0,1,0,-1};
int lnod[maxn<<2],rnod[maxn<<2],lcol[maxn<<2],rcol[maxn<<2],lnum[maxn<<2],rnum[maxn<<2],lazy[maxn<<2],lsh[maxn],n;
struct node
{
int l,r;
char ch;
}op[3000];
int getid(int x)
{
return lower_bound(lsh+1,lsh+n+1,x)-lsh;
}
inline void pushup(int rt,int L,int R)
{
int mid=(L+R)>>1;
if(lcol[ls]==0)
lcol[rt]=0,lnum[rt]=0;
else
{
lcol[rt]=1;
if(lnum[ls]==(mid-L+1))
{
if(lcol[rs]==1)
lnum[rt]=lnum[ls]+lnum[rs];
else
lnum[rt]=lnum[ls];
}
else
lnum[rt]=lnum[ls];
}
if(rcol[rs]==0)
rcol[rt]=0,rnum[rt]=0;
else
{
rcol[rt]=1;
if(rnum[rs]==(R-(mid+1)+1))
{
if(rcol[ls]==1)
rnum[rt]=rnum[rs]+rnum[ls];
else
rnum[rt]=rnum[rs];
}
else
rnum[rt]=rnum[rs];
}
if(rnod[ls]==-1&&rnod[rs]==-1)
rnod[rt]=lnod[rt]=-1;
else
if(rnod[ls]!=-1&&rnod[rs]==-1)
rnod[rt]=rnod[ls],lnod[rt]=lnod[ls];
else
if(rnod[ls]==-1&&rnod[rs]!=-1)
rnod[rt]=rnod[rs],lnod[rt]=lnod[rs];
else
if(rnod[ls]!=-1&&rnod[rs]!=-1)
{
if(rnod[ls]-lnod[ls]+1>=rnod[rs]-lnod[rs]+1)
rnod[rt]=rnod[ls],lnod[rt]=lnod[ls];
else
rnod[rt]=rnod[rs],lnod[rt]=lnod[rs];
if(rcol[ls]==1&&lcol[rs]==1)
{
int s=lsh[mid-rnum[ls]+1],e=lsh[mid+1+lnum[rs]-1];//
if(rnod[rt]-lnod[rt]+1<e-s+1)
rnod[rt]=e,lnod[rt]=s;
else
if((rnod[rt]-lnod[rt]+1==e-s+1)&&lnod[rt]>s)
rnod[rt]=e,lnod[rt]=s;
}
}
}
inline void pushdown(int rt,int L,int R)
{
if(lazy[rt]!=-1)
{
int mid=(L+R)>>1;
lazy[ls]=lazy[rs]=lazy[rt];
lcol[ls]=rcol[ls]=lcol[rs]=rcol[rs]=lazy[rt];
if(lazy[rt]==1)
lnum[ls]=rnum[ls]=mid-L+1,lnum[rs]=rnum[rs]=R-(mid+1)+1,lnod[ls]=lsh[L],rnod[ls]=lsh[mid],lnod[rs]=lsh[mid+1],rnod[rs]=lsh[R];
else
lnum[ls]=rnum[ls]=0,lnum[rs]=0,rnum[rs]=0,lnod[ls]=-1,rnod[ls]=-1,lnod[rs]=-1,rnod[rs]=-1;
lazy[rt]=-1;
}
}
inline void build(int rt,int L,int R)
{
lazy[rt]=-1;
if(L==R)
{
lnod[rt]=rnod[rt]=-1;
lcol[rt]=rcol[rt]=lnum[rt]=rnum[rt]=0;
return ;
}
int mid=(L+R)>>1;
build(ls,L,mid);
build(rs,mid+1,R);
pushup(rt,L,R);
}
inline void update(int rt,int L,int R,int l,int r,int v)
{
if(l<=L&&r>=R)
{
lazy[rt]=v;
lcol[rt]=rcol[rt]=v;
if(v==1)
lnum[rt]=rnum[rt]=R-L+1,lnod[rt]=lsh[L],rnod[rt]=lsh[R];
else
lnum[rt]=rnum[rt]=0,lnod[rt]=-1,rnod[rt]=-1;
return ;
}
if(v==1)
{
if((lcol[rt]==1&&lnum[rt]==R-L+1))
return ;
}
else
{
if(lnod[rt]==-1)
return ;
}
pushdown(rt,L,R);
int mid=(L+R)>>1;
if(r<=mid)
update(ls,L,mid,l,r,v);
else
if(l>mid)
update(rs,mid+1,R,l,r,v);
else
{
update(ls,L,mid,l,r,v);
update(rs,mid+1,R,l,r,v);
}
pushup(rt,L,R);
}
int main()
{
int root[100]={1,2,3,4,5,6,7,8,9};
int q;
while(scanf("%d",&q)!=EOF)
{
if(q==0) {printf("Oh, my god
");continue;}
n=0;
for(int i=1;i<=q;i++)
{
scanf("%d%d %c",&(op[i].l),&(op[i].r),&(op[i].ch));
lsh[++n]=op[i].l-1,lsh[++n]=op[i].l,lsh[++n]=op[i].r,lsh[++n]=op[i].r+1;
}
sort(lsh+1,lsh+n+1);
n=unique(lsh+1,lsh+n+1)-lsh-1;
build(1,1,n);
for(int i=1;i<=q;i++)
{
update(1,1,n,getid(op[i].l),getid(op[i].r),(op[i].ch=='w')?1:0);
}
if(lnod[1]==-1)
printf("Oh, my god
");
else
printf("%d %d
",lnod[1],rnod[1]);
}
return 0;
}