题目简意

有n个同学，每个同学有a,b,c三个数(c=a+b)

现在，有m次询问，每次给你三个数A,B,C问你满足a>=A,b>=B,c>=C的同学的人数

一道明显的三维偏序问题，只是空间把主席树卡了（别问我为什么知道qwq）

所以，这里我们就要打空间复杂度更小的cdq分治

我们先考虑下，怎么做题，因为我们肯定不能对每次询问都单独的做一次cdq分治，这样时间复杂度会原地爆炸，所以，我们可以考虑把所有询问存下来，一起做

我们可以把每个询问看做一个学生，这样，我们只需要求出比这些“学生”三个属性都大的学生（不包括询问产生的“学生”）的个数即可

那么， 我们就可以直接上cdq分治。
我们先按a由大到小排序（如果相等，将“学生”放后面，以保证可以询问的时候，符合条件的都添加好了）

然后，我们再在cdq分治中，按b由大到小做归并排序，同时，因为我们只需要计算左边区间对右边区间的贡献，所以，我们按顺序，将左边区间的所有学生（同样不包括询问）加入一个数据结构（我是权值线段树），对于右边区间，我们对所有“学生”进行查询操作即可~

需要注意的是，为了方便进行值的查询，我们最好先将数据进行离散化（反正只需要知道大小关系即可）
代码：

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+1;
int laz[N<<2],W[N<<2];
struct node{
    int a,b,c,num;
}q[N<<1];
struct lsh{
    int x,w;
}p[N<<1];
int ans[N];
inline bool kkk(lsh x,lsh y){
    return x.w<y.w;
}
inline bool ttt(node x,node y){
    return x.a!=y.a?x.a>y.a:x.num<y.num;
}
inline void down(int now,int l,int r){
    if(laz[now]){
        laz[now]=0;
        if(l==r){
            return;
        }
        W[now<<1]=W[now<<1|1]=0;
        laz[now<<1]=laz[now<<1|1]=1;
    }
}
inline void insert(int now,int l,int r,int x){
    down(now,l,r);
    ++W[now];
    if(l==r){
        return;
    }
    int mid=(l+r)>>1;
    if(x<=mid){
        insert(now<<1,l,mid,x);
    }else{
        insert(now<<1|1,mid+1,r,x);
    }
}
inline int find(int now,int l,int r,int lc,int rc){
    down(now,l,r);
    if(lc<=l&&r<=rc){
        return W[now];
    }
    int mid=(l+r)>>1,res=0;
    if(lc<=mid){
        res+=find(now<<1,l,mid,lc,rc);
    }
    if(rc>mid){
        res+=find(now<<1|1,mid+1,r,lc,rc);
    }
    return res;
}
int n,Q,tot;
node a[N];
inline bool ppp(node x,node y){
    return x.b!=y.b?x.b>y.b:x.num<y.num;
}
inline void cdq(int l,int r){
    if(l==r){
        return;
    }
    int mid=(l+r)>>1,al=0;
    cdq(l,mid),cdq(mid+1,r);
    //对答案加上左边对右边的贡献即可
    //两边已按1.q[i].b，2.q[i].num由大到小排序
    W[1]=0,laz[1]=1;//clear
    int L=l,R=mid+1;//两边指针
    while(L<=mid&&R<=r){
        if(ppp(q[L],q[R])){
            //将q[L]放入
            if(!q[L].num){
                insert(1,1,n,q[L].c);
            }
            a[++al]=q[L++];
        }else{
            if(q[R].num){
                ans[q[R].num]+=find(1,1,n,q[R].c,n);
            }
            a[++al]=q[R++];
        }
    }
    while(L<=mid){
        if(!q[L].num){
            insert(1,1,n,q[L].c);
        }
        a[++al]=q[L++];
    }
    while(R<=r){
        if(q[R].num){
            ans[q[R].num]+=find(1,1,n,q[R].c,n);
        }
        a[++al]=q[R++];
    }
    for(int i=l;i<=r;++i){//排序完毕~
        q[i]=a[i-l+1];
    }
}
int main(){
    scanf("%d%d",&n,&Q);
    for(int i=1;i<=n;++i){
        scanf("%d%d",&q[i].a,&q[i].b);
        q[i].c=q[i].a+q[i].b;q[i].num=0;
    }
    for(int i=1;i<=Q;++i){
        scanf("%d%d%d",&q[n+i].a,&q[n+i].b,&q[n+i].c);
        q[n+i].num=i;
    }
    //离散化
    n=n+Q;
    for(int i=1;i<=n;++i){
        p[i].x=i,p[i].w=q[i].a;
    }
    sort(p+1,p+n+1,kkk);
    q[p[1].x].a=tot=1;
    for(int i=2;i<=n;++i){
        if(p[i].w!=p[i-1].w){
            ++tot;
        }
        q[p[i].x].a=tot;
    }
    for(int i=1;i<=n;++i){
        p[i].x=i,p[i].w=q[i].b;
    }
    sort(p+1,p+n+1,kkk);
    q[p[1].x].b=tot=1;
    for(int i=2;i<=n;++i){
        if(p[i].w!=p[i-1].w){
            ++tot;
        }
        q[p[i].x].b=tot;
    }
    for(int i=1;i<=n;++i){
        p[i].x=i,p[i].w=q[i].c;
    }
    sort(p+1,p+n+1,kkk);
    q[p[1].x].c=tot=1;
    for(int i=2;i<=n;++i){
        if(p[i].w!=p[i-1].w){
            ++tot;
        }
        q[p[i].x].c=tot;
    }
    //三维偏序
    sort(q+1,q+n+1,ttt);
    //先按A由大到小排序
    cdq(1,n);
    for(int i=1;i<=Q;++i){
        printf("%d\n",ans[i]);
    }
    return 0;
}