首页 > 代码库 > hdu1199 线段树

hdu1199 线段树

2024-08-03 22:02:45   210人阅读

这题说的是给了 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\n",ansL, ansR);      }    }    return 0;}
View Code

 

hdu1199 线段树


联系
我们