一段长度未知的线段。一种操作:a b c ,表示区间[a,b]涂为颜色C,w代表白色,b代表黑色,问终于的最长连续白色段,输出起始位置和终止位置
离散化处理。和寻常的离散化不同,须要把点化成线段。左闭右开,即对于一段区间[a。b],转化成区间[a,b+1)
#include "stdio.h"#include "string.h"#include "algorithm"using namespace std;struct node{ int l,r,x;}data[20010];struct Mark{ int l,r,op;}mark[20010];struct B{ int id,x,dir;}b[20010];int color[20010];bool cmp(B a,B b){ return a.x=r) return ; data[k].l=l; data[k].r=r; data[k].x=0; if (l==r-1) return ; mid=(l+r)/2; build(l,mid,k*2); build(mid,r,k*2+1);}void updata(int l,int r,int k,int op){ int mid; if (l>=r) return ; if (data[k].l==l && data[k].r==r) { data[k].x=op; return ; } if (data[k].x!=-1 && data[k].x!=op) { data[k*2].x=data[k*2+1].x=data[k].x; data[k].x=-1; } mid=(data[k].l+data[k].r)/2; if (r<=mid) updata(l,r,k*2,op); else if (l>=mid) updata(l,r,k*2+1,op); else { updata(l,mid,k*2,op); updata(mid,r,k*2+1,op); }}void query(int k){ int i; if (data[k].l>=data[k].r) return ; if (data[k].x!=-1) { for (i=data[k].l;i ans) { ans=r-l; ans_l=l; ans_r=r; } } if (ans==0) printf("Oh, my god\n"); else printf("%d %d\n",ans_l,ans_r-1); } return 0;}