题解 P4348 【[CERC2015]Cow Confinement】

线段树加扫描线维护答案的差分。加花单点加 1，查询后缀和。

加入右区间时把绿色点加上蓝色区域的值（实际上不是到底，而是到下一个栅栏）（因为我们新加入两条栅栏后就走不下来了），然后把橘色区域清零（会被栅栏挡住）。

删除左区间时把棕色区域清零（会被栅栏挡住），并在粉色点减去紫色区域的值（去掉两条栅栏后，粉色点可能先下后右，或先右后下，会算重，所以减掉去重）。

注意排序顺序：先右区间，然后左区间，然后加花，最后查询。

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

//starusc
#include<bits/stdc++.h>
using namespace std;
inline int read(){
    int x=0,f=1,c=getchar();
    while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
    while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
    return f==1?x:-x;
}
const int N=2e5+4,M=1e6+4,mx=1e6+1;
namespace seg{
    #define lc (p<<1)
    #define rc (p<<1|1)
    int t[M<<2],lz[M<<2];
    inline void pushdown(int p,int l,int r){
        if(!lz[p])return;
        lz[lc]=lz[rc]=1;
        t[lc]=t[rc]=0;
        lz[p]=0;
    }
    inline void pushup(int p){
        t[p]=t[lc]+t[rc];
    }
    void modify(int p,int l,int r,int x,int v){
        if(l==r){
            t[p]+=v;
            return;
        }
        pushdown(p,l,r);
        int mid=(l+r)>>1;
        if(x<=mid)modify(lc,l,mid,x,v);
        else modify(rc,mid+1,r,x,v);
        pushup(p); 
    }
    void cover(int p,int l,int r,int ql,int qr){
        if(ql<=l&&r<=qr){
            lz[p]=1;
            t[p]=0;
            return;
        }
        pushdown(p,l,r);
        int mid=(l+r)>>1;
        if(ql<=mid)cover(lc,l,mid,ql,qr);
        if(mid<qr)cover(rc,mid+1,r,ql,qr);
        pushup(p);
    }
    int query(int p,int l,int r,int ql,int qr){
        if(ql<=l&&r<=qr)return t[p];
        pushdown(p,l,r);
        int mid=(l+r)>>1;
        if(qr<=mid)return query(lc,l,mid,ql,qr);
        if(mid<ql)return query(rc,mid+1,r,ql,qr);
        return query(lc,l,mid,ql,qr)+query(rc,mid+1,r,ql,qr);
    }
    #undef lc
    #undef rc
}
struct ques{
    int x,yl,yr,id,op;
}q[N<<2];
inline bool comp(const ques &a,const ques &b){//op!顺序问题 
    if(a.x!=b.x)return a.x>b.x;
    return a.op<b.op;
}
int n,tot,ans[N],tmp[N];
multiset<int>s;
int main(){
    freopen("cow.in","r",stdin);
    freopen("cow.out","w",stdout);
    n=read();
    for(int i=1,a1,b1,a2,b2;i<=n;i++){
        a1=read();b1=read();a2=read();b2=read();
        q[++tot]=(ques){a2,b1,b2,i,1};
        q[++tot]=(ques){a1-1,b1,b2,-i,2};
    } 
    n=read();
    for(int i=1,x,y;i<=n;i++){
        x=read();y=read();
        q[++tot]=(ques){x,y,0,0,3};
    }
    n=read();
    for(int i=1,x,y;i<=n;i++){
        x=read();y=read();
        q[++tot]=(ques){x,y,i,0,4};
    }
    sort(q+1,q+tot+1,comp);
    s.insert(mx);
    for(int i=1,nxt;i<=tot;i++){
        if(q[i].id){
            if(q[i].id>0){
                nxt=(*s.upper_bound(q[i].yr));
                tmp[q[i].id]=seg::query(1,0,mx,q[i].yr+1,nxt);
                seg::modify(1,0,mx,q[i].yl-1,seg::query(1,0,mx,q[i].yl,nxt));
                seg::cover(1,0,mx,q[i].yl,q[i].yr);
                s.insert(q[i].yl-1);
                s.insert(q[i].yr);
            }
            else{
                seg::modify(1,0,mx,q[i].yl-1,-tmp[-q[i].id]);
                seg::cover(1,0,mx,q[i].yl,q[i].yr);
                s.erase(s.find(q[i].yl-1));
                s.erase(s.find(q[i].yr));
            }
        }
        else if(!q[i].yr){
            seg::modify(1,0,mx,q[i].yl,1);
        }
        else{
            nxt=(*s.lower_bound(q[i].yl));
            ans[q[i].yr]=seg::query(1,0,mx,q[i].yl,nxt);
        }
    }
    for(int i=1;i<=n;i++)cout<<ans[i]<<"\n";
    return (0-0);
}