P2163 【[SHOI2007]园丁的烦恼】

其实是不用把一个询问拆成四个的

把询问转化为数学语言：

对于每个查询，询问满足$a<=x<=b$且$c<=y<=d$的点$x,y$的个数

~~自然~~想到偏序问题，看到有两个式子，二维偏序？好像办不到，反正我不会

如何升维，拆分即可

把原式拆成$a<=x,x<=b,c<=y,y<=d$，这样就可以用四维偏序解决了，但是这样的复杂度显然是不能保证的

尝试降维

如果这样呢$a<=x,x<=b,c<=y<=d$

对于一个点，我们定义其三个维度为：

$a,b->x$即以横坐标作为第一维和第二维

$c->y$即以纵坐标作为第三维

而查询，依照上式，我们定义其维度

以$a$为第一维，$c$为第二维，$b,d$为三维和四维（查询用）

所以三维偏序的式子就是

$a_i<=a_j,b_i>=b_j,c_i<=c_j<=d_i$

考虑重复元素的贡献问题，记得排序时加上$c$相同，按$d$排

上代码（其实是要写离散化的，但是我懒得写，拿$O2$替了）

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<vector>

using namespace std;

const int maxn=5e5+,maxl=1e7+;

struct node{

    int a,b,c,d,w,mp;

}v[*maxn];

int n,m,c[maxl],ans[maxn];

bool cmpy(const node &a,const node &b)

{

    return a.b==b.b?(a.c==b.c?a.d<b.d:a.c>b.c):a.b<b.b;

}

bool cmpx(const node &a,const node &b)

{

    return a.a==b.a?cmpy(a,b):a.a>b.a;

}

int lowbit(int x)

{

    return x&-x;

}

void add(int x,int ch)

{

    while(x<=maxl-)

    {

        c[x]+=ch;

        x+=lowbit(x);

    }

}

int sum(int x)

{

    int ret=;

    while(x)

    {

        ret+=c[x];

        x-=lowbit(x);

    }

    return ret;

}

void cdq(int l,int r)

{

    if(l==r)

        return;

    int mid=l+r>>;

    cdq(l,mid),cdq(mid+,r);

    sort(v+l,v+mid+,cmpy),sort(v+mid+,v+r+,cmpy);

    int i=l,j=mid+;

    for(;j<=r;j++)

    {

        while(v[i].b<=v[j].b&&i<=mid)

            add(v[i].c,v[i].w),i++;

        ans[v[j].mp]+=sum(v[j].d)-sum(v[j].c-);

    }

    for(j=l;j<i;j++)

        add(v[j].c,-v[j].w);

}

int main()

{

    scanf("%d%d",&n,&m);

    for(int i=;i<=n;i++)

    {

        scanf("%d%d",&v[i].a,&v[i].c);

        v[i].a++,v[i].c++;

        v[i].b=v[i].a,v[i].w=,v[i].d=v[i].mp=;

    }

    for(int i=n+;i<=n+m;i++)

    {

        scanf("%d%d%d%d",&v[i].a,&v[i].c,&v[i].b,&v[i].d);

        v[i].a++,v[i].b++,v[i].c++,v[i].d++;

        v[i].w=,v[i].mp=i-n;

    }

    sort(v+,v+n+m+,cmpx);

    cdq(,n+m);

    for(int i=;i<=m;i++)

        printf("%d\n",ans[i]);

    return ;

}