BZOJ2652 : 三角板

时间：2023-12-18 22:10:56

首先旋转坐标系，假设$(x,y)$被$(X,Y)$遮挡等价于$X\leq x$且$Y\leq y$。

对于每种坐标系建立两棵线段树：

第一棵按$x$维护已经加入的点的$y$的最小值；

第二棵按$x$维护看得见的点的$y$的最大值。

对于一块三角板，通过第一棵线段树查询即可知道是否可以放下，然后在第二棵线段树中不断找到被遮挡的点并删除。

时间复杂度$O(n\log n)$。

#include<cstdio>

#include<algorithm>

typedef long long ll;

using namespace std;

typedef pair<ll,int>P;

const int N=100010,M=262150;

const ll inf=1LL<<60;

int n,i,x,y,ans;char ch[5],f[N];ll a[N];

inline bool cmp(int x,int y){return a[x]<a[y];}

struct DS{

ll a[N],b[N],A,B,C,D,mi[M];P ma[M];

int c[N],rk[N],st[N],en[N],pos[N];

void init(ll _A,ll _B,ll _C,ll _D){A=_A,B=_B,C=_C,D=_D;}

inline void build(int x,int a,int b){

  mi[x]=inf,ma[x]=P(-inf,0);

  if(a==b){pos[a]=x;return;}

  int mid=(a+b)>>1;

  build(x<<1,a,mid),build(x<<1|1,mid+1,b);

}

inline void changemi(int x,ll a){for(x=pos[x];x;x>>=1)mi[x]=min(mi[x],a);}

inline void changema(int x,P b){

  ma[x=pos[x]]=b;

  for(x>>=1;x;x>>=1)ma[x]=max(ma[x<<1],ma[x<<1|1]);

}

ll askmi(int x,int a,int b,int c,int d){

  if(c<=a&&b<=d)return mi[x];

  int mid=(a+b)>>1;ll t=inf;

  if(c<=mid)t=askmi(x<<1,a,mid,c,d);

  if(d>mid)t=min(t,askmi(x<<1|1,mid+1,b,c,d));

  return t;

}

P askma(int x,int a,int b,int c,int d){

  if(c<=a&&b<=d)return ma[x];

  int mid=(a+b)>>1;P t=P(-inf,0);

  if(c<=mid)t=askma(x<<1,a,mid,c,d);

  if(d>mid)t=max(t,askma(x<<1|1,mid+1,b,c,d));

  return t;

}

inline void set(int i,int x,int y){

  a[i]=A*x+B*y;

  b[i]=C*x+D*y;

  c[i]=i;

}

void pre(){

  int i,j,k;

  for(i=1;i<=n;i++)::a[i]=a[i];

  sort(c+1,c+n+1,cmp);

  for(i=1;i<=n;i++)rk[c[i]]=i;

  for(i=1;i<=n;i=j){

    for(j=i;j<=n&&a[c[i]]==a[c[j]];j++);

    for(k=i;k<j;k++)st[c[k]]=i,en[c[k]]=j-1;

  }

  build(1,1,n);

}

inline bool check(int i){return askmi(1,1,n,1,en[i])>b[i];}

}T[2];

inline void del(int o,int x){

  while(1){

    P t=T[o].askma(1,1,n,T[o].st[x],n);

    if(t.first<T[o].b[i])return;

    ans--;

    T[0].changema(T[0].rk[t.second],P(-inf,0));

    T[1].changema(T[1].rk[t.second],P(-inf,0));

  }

}

inline void read(int&a){

  char c;bool f=0;a=0;

  while(!((((c=getchar())>='0')&&(c<='9'))||(c=='-')));

  if(c!='-')a=c-'0';else f=1;

  while(((c=getchar())>='0')&&(c<='9'))(a*=10)+=c-'0';

  if(f)a=-a;

}

int main(){

  T[0].init(2,-1,-2,-1);

  T[1].init(1,-1,-1,-1);

  read(n);

  for(i=1;i<=n;i++){

    read(x),read(y);

    scanf("%s",ch);

    f[i]=ch[0]=='W';

    T[0].set(i,x,y);

    T[1].set(i,x,y);

  }

  T[0].pre();

  T[1].pre();

  for(i=1;i<=n;i++)if(T[0].check(i)&&T[1].check(i)){

    del(f[i],i);

    T[f[i]].changemi(T[f[i]].rk[i],T[f[i]].b[i]);

    T[0].changema(T[0].rk[i],P(T[0].b[i],i));

    T[1].changema(T[1].rk[i],P(T[1].b[i],i));

    ans++;

    printf("%d\n",ans);

  }else puts("FAIL");

  return 0;

}

　　

相关文章