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+10,maxl=1e7+10;
struct node{
    int a,b,c,d,w,mp;
}v[2*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-9)
    {
        c[x]+=ch;
        x+=lowbit(x);
    }
}
int sum(int x)
{
    int ret=0;
    while(x)
    {
        ret+=c[x];
        x-=lowbit(x);
    }
    return ret;
}
void cdq(int l,int r)
{
    if(l==r)
        return;
    int mid=l+r>>1;
    cdq(l,mid),cdq(mid+1,r);
    sort(v+l,v+mid+1,cmpy),sort(v+mid+1,v+r+1,cmpy);
    int i=l,j=mid+1;
    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-1);
    }
    for(j=l;j<i;j++)
        add(v[j].c,-v[j].w);
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;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=1,v[i].d=v[i].mp=0;
    }
    for(int i=n+1;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=0,v[i].mp=i-n;
    }
    sort(v+1,v+n+m+1,cmpx);
    cdq(1,n+m);
    for(int i=1;i<=m;i++)
        printf("%d
",ans[i]);
    return 0;
}

P2163 【[SHOI2007]园丁的烦恼】

相关推荐