题解 | #枇杷#

原题解链接：

题面有个隐含条件是直角梯形的三角形部分是等腰直角三角形，问题转化为求矩形+等腰直角三角形点权和。

对于所有在等腰直角三角形斜边上的点$(x,y)(x,y)$，满足$x+yx\; +\; y$是一个定值$kk$。

考虑$CDQCDQ$分治求矩形内部点权和的过程，如果以横坐标为排序的第一关键字， 纵坐标为排序的第二关键字，当前扫到一个询问二元组$(2,y)(2,\; y)$的话，实际上求的是所有横坐标$\le x\le \; x$且纵坐标$\le y\le y$的点数。

类比这个,我们以横坐标加纵坐标为排序的第二关键字,那求的实际上就是横坐标$\le x\le x$且纵坐标$\le x+y\le x\; +\; y$的点数，也就是这幅图里红线和坐标轴交点以内的总点数。

于是可以做一遍$CDQCDQ$分治求出下图中黄***域的总点数,再做一遍$CDQCDQ$减去下面的矩形就可以了。

梯形中的矩形也可以在第二遍$CDQCDQ$顺便求出。

#include<cstdio>
#include<cctype>
#include<cstring>
#include<algorithm>
#define N 100005
#define re register
#define ll long long
// #define int long long
#define min(A,B) ((A)<(B)?(A):(B))
#define max(A,B) ((A)>(B)?(A):(B))
#define swap(A,B) ((A)^=(B)^=(A)^=(B))

int n,tot;
int g[N*10],op[N],cnt;
int x2d[N],xyd[N],x21[N];
ll x[N],y[N],x2[N],d[N];
ll f[N*10],jl[N*10],ans[N];
//type:0->add  2->add to the ans 1->minus to the ans
struct Node{
    int idx,x,xx,xy,now,type;
}node[N*10],node2[N*10];

int getint(){
    int x=0,f=0;char ch=getchar();
    while(!isdigit(ch)) f|=ch=='-',ch=getchar();
    while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    return f?-x:x;
}

void add(int x,const ll &y){
    while(x<=tot)
        f[x]+=y,x+=x&-x;
}

ll query(int x){
    ll now=0;
    while(x)
        now+=f[x],x-=x&-x;
    return now;
}

void cdq(int l,int r){
    if(l==r) return;int mid=l+r>>1;
    cdq(l,mid);cdq(mid+1,r);
    re int a=l,b=mid+1,now=l;
    while(a<=mid and b<=r){
        if(node[a].x<node[b].x)
            node2[now++]=node[a++];
        else if(node[a].x>node[b].x)
            node2[now++]=node[b++];
        else if(node[a].xx<node[b].xx)
            node2[now++]=node[a++];
        else if(node[a].xx>node[b].xx)
            node2[now++]=node[b++];
        else if(!node[a].type)
            node2[now++]=node[a++];
        else
            node2[now++]=node[b++];
    }
    while(a<=mid) node2[now++]=node[a++];
    while(b<=r) node2[now++]=node[b++];
    for(re int i=l;i<=r;i++){
        node[i]=node2[i];
        if(node[i].type)
            jl[node[i].xx]=query(node[i].xx);
    }
    for(re int i=l;i<=r;i++){
        if(!node[i].type){
            if(node[i].now<=mid){
                add(node[i].xx,1);
            }
        } else{
            if(node[i].now>mid){
                ll q=query(node[i].xx)-jl[node[i].xx];
                if(node[i].type==1)
                    ans[node[i].idx]-=q;
                else
                    ans[node[i].idx]+=q;
            }
        }
    }
}

void cdq2(int l,int r){
    if(l==r) return;int mid=l+r>>1;
    cdq2(l,mid);cdq2(mid+1,r);
    re int a=l,b=mid+1,now=l;
    while(a<=mid and b<=r){
        if(node[a].x<node[b].x)
            node2[now++]=node[a++];
        else if(node[a].x>node[b].x)
            node2[now++]=node[b++];
        else if(!node[a].type)
            node2[now++]=node[a++];
        else if(!node[b].type)
            node2[now++]=node[b++];
        else
            node2[now++]=node[a++];
    }
    while(a<=mid) node2[now++]=node[a++];
    while(b<=r) node2[now++]=node[b++];
    for(re int i=l;i<=r;i++){
        node[i]=node2[i];
        if(node[i].type)
            jl[node[i].xx]=query(node[i].xx),jl[node[i].xy]=query(node[i].xy);
    }
    for(re int i=l;i<=r;i++){
        if(!node[i].type){
            if(node[i].now<=mid)
                add(node[i].xx,1);
        } else{
            if(node[i].now>mid){
                if(node[i].type==1)
                    ans[node[i].idx]-=query(node[i].xy)-jl[node[i].xy]-query(node[i].xx)+jl[node[i].xx];
                else
                    ans[node[i].idx]+=query(node[i].xy)-jl[node[i].xy]-query(node[i].xx)+jl[node[i].xx];
            }
        }
    }
}

signed main(){
    // freopen("in1.in","r",stdin);freopen("out.txt","w",stdout);
    n=getint();
    for(re int i=1;i<=n;i++){
        op[i]=getint();
        if(op[i]==1){
            x[i]=getint(),y[i]=getint();
            g[++tot]=x[i];g[++tot]=y[i];g[++tot]=x[i]+y[i];
        } else{
            x[i]=getint(),y[i]=getint(),x2[i]=getint(),d[i]=getint();
            g[++tot]=x2[i]+y[i]+d[i];g[++tot]=x2[i]-1;g[++tot]=x2[i]+d[i];g[++tot]=y[i]-1;g[++tot]=y[i]+d[i];g[++tot]=x[i]-1;
        }
    } g[++tot]=0;
    std::sort(g+1,g+1+tot);tot=std::unique(g+1,g+1+tot)-g-1;
    for(re int i=1;i<=n;i++){
        if(op[i]==1){
            int p=std::lower_bound(g+1,g+1+tot,x[i])-g;//
            node[++cnt].idx=i;node[cnt].type=0;node[cnt].x=p;node[cnt].xx=std::lower_bound(g+1,g+1+tot,x[i]+y[i])-g;node[cnt].xy=0;node[cnt].now=cnt;x[i]=p;y[i]=std::lower_bound(g+1,g+1+tot,y[i])-g;
        } else{
            x21[i]=std::lower_bound(g+1,g+1+tot,x2[i]-1)-g;xyd[i]=std::lower_bound(g+1,g+1+tot,x2[i]+y[i]+d[i])-g;x2d[i]=std::lower_bound(g+1,g+1+tot,x2[i]+d[i])-g;
            node[++cnt].idx=i;node[cnt].type=1;node[cnt].x=x21[i];node[cnt].xx=xyd[i];node[cnt].xy=0;node[cnt].now=cnt;
            node[++cnt].idx=i;node[cnt].type=2;node[cnt].x=x2d[i];node[cnt].xx=node[cnt-1].xx;node[cnt].xy=0;node[cnt].now=cnt;
        }
    }
    cdq(1,cnt);
    cnt=0;
    for(re int i=1;i<=n;i++){
        if(op[i]==1){
            node[++cnt].idx=i;node[cnt].type=0;node[cnt].x=x[i];node[cnt].xx=y[i];node[cnt].xy=0;node[cnt].now=cnt;
        } else{
            node[++cnt].idx=i;node[cnt].type=1;node[cnt].x=x2d[i];node[cnt].xy=std::lower_bound(g+1,g+1+tot,y[i]-1)-g;node[cnt].xx=1;node[cnt].now=cnt;
            node[++cnt].idx=i;node[cnt].type=2;node[cnt].x=x21[i];node[cnt].xy=node[cnt-1].xy;node[cnt].xx=1;node[cnt].now=cnt;
            node[++cnt].idx=i;node[cnt].type=1;node[cnt].x=std::lower_bound(g+1,g+1+tot,x[i]-1)-g;node[cnt].xx=node[cnt-2].xy;node[cnt].xy=std::lower_bound(g+1,g+1+tot,y[i]+d[i])-g;node[cnt].now=cnt;
            node[++cnt].idx=i;node[cnt].type=2;node[cnt].x=x21[i];node[cnt].xx=node[cnt-1].xx;node[cnt].xy=node[cnt-1].xy;node[cnt].now=cnt;
        }
    }
    cdq2(1,cnt);
    for(re int i=1;i<=n;i++)
        if(op[i]==2)
            printf("%lld\n",ans[i]);
    return 0;
}