BZOJ4422 : [Cerc2015]Cow Confinement-蒲公英云

BZOJ4422 : [Cerc2015]Cow Confinement

r囧r小猫 2022-03-30 10:16 230阅读 0赞

从右往左扫描线，用线段树维护扫描线上每一个点能达到的花的数量，并支持最近篱笆的查询。

对于一朵花，找到它上方最近的篱笆，那么它对这中间的每头牛的贡献都是$1$。

当扫到一个篱笆的右边界时，这中间的答案都要清零。

当扫到一个篱笆的左边界时，这中间的答案同理都要清零，但是要向上直到最近的篱笆为止都加上下面的答案。

这中间对这个篱笆右下角的贡献会重复计数，因此需要减掉。

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

#include<cstdio>
#include<algorithm>
const int N=1000005,M=2100000,U=200010;
int n,m,cnt,i,v[M],ta[M],tc[M],f[U],ans[U];
struct E{
  int x,l,r,t,i;
  E(){}
  E(int _x,int _l,int _r,int _t,int _i){x=_x,l=_l,r=_r,t=_t,i=_i;}
}e[U*5];
inline bool cmp(const E&a,const E&b){
  if(a.x!=b.x)return a.x>b.x;
  if(a.t!=b.t)return a.t<b.t;
  return a.l<b.l;
}
inline void read(int&a){char c;while(!(((c=getchar())>='0')&&(c<='9')));a=c-'0';while(((c=getchar())>='0')&&(c<='9'))(a*=10)+=c-'0';}
inline void taga1(int x,int p){if(~tc[x])tc[x]+=p;else ta[x]+=p;}
inline void tagc1(int x,int p){ta[x]=0;tc[x]=p;}
inline void pb(int x){
  if(ta[x])taga1(x<<1,ta[x]),taga1(x<<1|1,ta[x]),ta[x]=0;
  if(~tc[x])tagc1(x<<1,tc[x]),tagc1(x<<1|1,tc[x]),tc[x]=-1;
}
void change(int x,int a,int b,int c,int p){
  if(a==b){v[x]=p?a:0;return;}
  int mid=(a+b)>>1;
  c<=mid?change(x<<1,a,mid,c,p):change(x<<1|1,mid+1,b,c,p);
  v[x]=v[x<<1|1]?v[x<<1|1]:v[x<<1];
}
int get(int x,int a,int b,int d){
  if(b<=d)return v[x];
  int mid=(a+b)>>1,t=0;
  if(d>mid)t=get(x<<1|1,mid+1,b,d);
  if(t)return t;
  return get(x<<1,a,mid,d);
}
void add(int x,int a,int b,int c,int d,int p){
  if(c<=a&&b<=d){taga1(x,p);return;}
  pb(x);
  int mid=(a+b)>>1;
  if(c<=mid)add(x<<1,a,mid,c,d,p);
  if(d>mid)add(x<<1|1,mid+1,b,c,d,p);
}
void clear(int x,int a,int b,int c,int d){
  if(c<=a&&b<=d){tagc1(x,0);return;}
  pb(x);
  int mid=(a+b)>>1;
  if(c<=mid)clear(x<<1,a,mid,c,d);
  if(d>mid)clear(x<<1|1,mid+1,b,c,d);
}
int ask(int x,int a,int b,int c){
  if(a==b)return ta[x]+tc[x];
  pb(x);
  int mid=(a+b)>>1;
  return c<=mid?ask(x<<1,a,mid,c):ask(x<<1|1,mid+1,b,c);
}
int main(){
  read(m);
  for(i=1;i<=m;i++){
    int xl,xr,yl,yr;
    read(xl),read(yl),read(xr),read(yr);
    e[++cnt]=E(yr,xl,xr,-2,0);
    e[++cnt]=E(yl-1,xl,xr,-1,i);
    e[++cnt]=E(yr+1,xr+1,0,1,-i);
  }
  read(m);
  while(m--){
    int x,y;
    read(x),read(y);
    e[++cnt]=E(y,x,0,0,0);
  }
  read(n);
  for(i=1;i<=n;i++){
    int x,y;
    read(x),read(y);
    e[++cnt]=E(y,x,0,1,i);
  }
  std::sort(e+1,e+cnt+1,cmp);
  for(i=1;i<=cnt;i++){
    int l=e[i].l,r=e[i].r;
    if(e[i].t==-1){
      change(1,0,N,l-1,0);
      change(1,0,N,r,0);
      int o=get(1,0,N,l-1);
      clear(1,0,N,l,r);
      add(1,0,N,o+1,r,ask(1,0,N,r+1));
      if(o+1<=l-1&&f[e[i].i])add(1,0,N,o+1,l-1,-f[e[i].i]);
    }else if(e[i].t==-2){
      change(1,0,N,l-1,1);
      change(1,0,N,r,1);
      clear(1,0,N,l,r);
    }else if(!e[i].t)add(1,0,N,get(1,0,N,l-1)+1,l,1);
    else{
      if(e[i].i>0)ans[e[i].i]=ask(1,0,N,l);
      else f[-e[i].i]=ask(1,0,N,l);
    }
  }
  for(i=1;i<=n;i++)printf("%d\n",ans[i]);
  return 0;
}