[SHOI2007]园丁的烦恼

Author Avatar
ZC 2月 07, 2019
  • 在其它设备中阅读本文章

[SHOI2007]园丁的烦恼

一道经典的数点问题。

看了题解基本都是写cdq分治/离散化的。

我用了一种非常简洁的方法。

因为可以离线,而且中间没有修改操作,那么接下来可以方便地处理了。

开一个树状数组记录$y$轴。

把一个询问拆为$4$个点,然后按二维前缀和的方式容斥。

设$(1,1)$到$(x,y)$中点数为$s(x,y)​$.

那么答案就为$s(c,d)-s(a-1,d)-s(c,b-1)+s(a-1,b-1)$ 。

我们先把给的点的坐标询问的坐标x轴坐标排序

然后枚举询问坐标,把点坐标中$x$轴坐标小于它的加进树状数组。

于是就愉快地a了这道题。

2333(经过一点玄学优化后拿了rk1)

如果上面不理解的话就再看下代码,一个就懂了。

一坨快读自行忽略

#include<cstdio>
#include<algorithm>
namespace FastIO{const char* ln="\n";struct Reader{char buf[1<<20],*s,*t;bool EOF_FLG;Reader():s(buf),t(buf),EOF_FLG(false) {};char gt() {return s==t&&((t=(s=buf)+fread(buf,1,1<<20,stdin))==s)?EOF:(*s++);}Reader& operator>>(char* str) {if(EOF_FLG)return *str=0,*this;while((*str=gt())!=' '&&*str!='\n'&&*str!=EOF)++str;if(*str==EOF)EOF_FLG=true;*str=0;return *this;}template<typename T>Reader&operator>>(T&x) {if(EOF_FLG)return *this;char c=0,d;while(c!=EOF&&(c<'0'||c>'9'))d=c,c=gt();if(c==EOF){EOF_FLG=true;return *this;}else x=0;while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+c-'0',c=gt();if(d=='-')x=-x;return *this;}}in;struct Writer{char buf[1<<20],*s,*t;Writer():s(buf),t(buf+(1<<20)){}~Writer(){fwrite(buf,1,s-buf,stdout);}void pt(char c){(s==t)?(fwrite(s=buf,1,1<<20,stdout),*s++=c):(*s++=c);}template<typename T>Writer&operator<<(T x){if(!x)return pt('0'),*this;if(x<0)pt('-'),x=-x;char a[40],t=0;while(x)a[t++]=x%10,x/=10;while(t--)pt(a[t]+'0');return *this;}Writer&operator<<(const char*s) {while(*s)pt(*s++);return *this;}}out;}using namespace FastIO;
#define Fur(i,x,y) for(int i=x;i<=y;i++)
using namespace std;
#define N 500000
int n,q;
struct node{
    int x,y,id,opt;
}a[N+1],b[N*4+1];
int tr[N+1],ans[N+1];
void add(int x){while(x<=N)tr[x]++,x+=(x&-x);};
int get(int x){int s=0;while(x)s+=tr[x],x-=(x&-x);return s;}
bool cmp(node x,node y){
    if(x.x!=y.x)return x.x<y.x;
    return x.y<y.y;
}
int main(){
    in>>n>>q;
    int d=0,x,y,xx,yy;
    Fur(i,1,n)in>>x>>y,a[i].x=x+1,a[i].y=y+1;
    sort(a+1,a+n+1,cmp);
    Fur(i,1,q){
        in>>x>>y>>xx>>yy;
        x++;y++;xx++;yy++;
        b[++d].x=x-1,b[d].y=y-1,b[d].opt=1,b[d].id=i;
        b[++d].x=x-1,b[d].y=yy,b[d].opt=-1,b[d].id=i;
        b[++d].x=xx,b[d].y=y-1,b[d].opt=-1,b[d].id=i;
        b[++d].x=xx,b[d].y=yy,b[d].opt=1,b[d].id=i;
    }
    sort(b+1,b+d+1,cmp);
    int j=1;
    Fur(i,1,d){
        while(j<=n&&a[j].x<=b[i].x)add(a[j].y),j++;
        ans[b[i].id]+=get(b[i].y)*b[i].opt;
    }
    Fur(i,1,q)out<<ans[i]<<ln;
}