BZOJ4422 : [Cerc2015]Cow Confinement

r囧r小猫 2022-03-30 10:16 122阅读 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;
    }