二维数点(一修)
万弘
·
·
个人记录
二维数点(一修)
二维数点的基本模型:
平面上有n个点,给出m个矩形(或正方形),求每一个矩形所包含的点的数量.
解法0:
值域太大,无法直接使用二维前缀和(即使进行离散化,空间也是$O(n^2)$的).
解法1:二维树状数组/二维线段树
没写过,但应该是可以做的,$O(log^2n)$每次查询.可在线.
解法2:离线排序+树状数组(经典做法)
用容斥,将查询$count(x1,y1,x2,y2)$拆成$count(0,y1,x2,y2)-count(0,y1,x1-1,y2)$,然后把这些询问用$(x,y1,y2,dex,op)$表示(dex表示属于第几个询问,op表示贡献是正还是负),按照x从小到达排序,对y坐标离散化,然后用树状数组维护y上的点的数量就好了.
给出例题[园丁的烦恼](https://www.luogu.org/problem/P2163) 的代码:
```cpp
/**********/省略快读
#define MAXN 2000011
ll n,m,k,fy[MAXN],f[MAXN],diffcnt=0;
struct BIT
{
ll t[MAXN];
#define lowb (i&-i)
void modify(ll i,ll k)
{
if(i==0)return;
while(i<=diffcnt)
{
t[i]+=k;
i+=lowb;
}
}
ll Qsum(ll i)
{
ll res=0;
while(i)
{
res+=t[i];
i-=lowb;
}
return res;
}
}t;
struct Query
{
ll x,y1,y2,dex,op;
Query(ll _x=0,ll _y1=0,ll _y2=0,ll _dex=0,ll _op=0)
{
x=_x,y1=_y1,y2=_y2,dex=_dex,op=_op;
}
bool operator <(const Query& t)
const
{
return x<t.x;
}
}q[MAXN];
pll a[MAXN];
ll place(ll val)
{
return std::lower_bound(fy+1,fy+diffcnt+1,val)-fy;
}
int main()
{
n=read(),m=read();
for(ll i=1;i<=n;++i)
{
a[i].first=read(),a[i].second=read();
fy[++diffcnt]=a[i].second;
}
ll cnt=0;
for(ll i=1;i<=m;++i)
{
ll x1=read(),y1=read(),x2=read(),y2=read();
q[++cnt]=Query(x1-1,y1-1,y2,i,-1);
q[++cnt]=Query(x2,y1-1,y2,i,1);
fy[++diffcnt]=y1-1,fy[++diffcnt]=y2;
}
std::sort(fy+1,fy+diffcnt+1);
diffcnt=std::unique(fy+1,fy+diffcnt+1)-fy-1;
std::sort(a+1,a+n+1);
std::sort(q+1,q+cnt+1);
ll it=1;
for(ll i=1;i<=cnt;++i)
{
while(it<=n&&a[it].first<=q[i].x)
{
t.modify(place(a[it].second),1);
++it;
}
f[q[i].dex]+=q[i].op*(t.Qsum(place(q[i].y2))-t.Qsum(place(q[i].y1)));
}
for(ll i=1;i<=m;++i)printf("%lld\n",f[i]);
return 0;
}
```