XSY 2060 - Rectangle Query

题目精选 压位

---

题意

  平面内给定 $n$ 个点 $(x_i,y_i)$ 。给定 $m$ 个询问，询问 以 $(x_1,y_1)$ 为左下角， $(x_2,y_2)$ 为右上角的矩形内，不同的横坐标和不同的纵坐标分别有多少个。
   $1\le n,m\le 50000$ ，强制在线

分析

  对每一个点 $x$ ，我们用一个四元组 $(x,y,prex,prey)$ 进行刻画。
   $x$ 表示它的横坐标， $y$ 表示它的纵坐标， $prex$ 表示与它相同的纵坐标的上一个横坐标， $prey$ 表示与它相同的横坐标的上一个纵坐标。
  那么，一个矩形 $[(x_1,y_1),(x_2,y_2)]$ 中的不同横坐标的个数，就是满足

$$\left\{\begin{aligned}&x_1\le x_i\le x_2\\&y_1\le y_i\le y_2\\&prex_i<y_1\end{aligned}\right.$$
的点 $i$ 的个数。
  纵坐标也类似，这里不展开讨论。

  我们在处理这种满足多个条件的问题时，一种想法就是先满足一个条件，然后再满足一个条件，对应着树套树、cdq分治等方法；还有一种想法就是分别求满足这几个条件的，然后合并起来。
  至于合并的方法就比较暴力了，我们考虑使用 bitset 进行优化。
  而且这道题的数据范围是 $n\le 50000$ ，一般这种复杂度都是进行一些 $\log^2 n$ 或者 $\sqrt n$ 或者 $\frac{n}{64}$ 这种没有 $\log n$ 优的方法。

  所以这道题，我们考虑对每个限制条件开 $n$ 个 bitset ，表示 $x\le x_2$ 的满足的位置。那么，预处理的时间复杂度为 $\frac{n^2}{64}$ ，空间为 $\frac{n^2}{64}$ 。查询的时间为 $\frac{mn}{64}$ 。然而发现这样会爆空间。

  我们考虑使用时间换空间。我们对每个限制条件开 $\sqrt n$ 个 bitset ，每个存 $x\le x_2$ 的满足的位置。那么，预处理的时间为 $\frac{n\sqrt n}{64}$ ，空间为 $\frac{n\sqrt n}{64}$ 。查询的时间为 $m(\frac{n}{64}+\sqrt n)=\frac{mn}{64}+m\sqrt n$ 。

实现

   bitset<N> 的空间估计：一个 long long 存 $64$ 位，所以共存了 $\frac{N}{64}$ 位，所以空间为 $\frac{\frac{N}{64}\times 8}{1024\times 1024}$ 。
   bitset<N> 的一些必须知道的功能： reset() flip() set() count()

  一种简易的离散化的写法：不需要 unique 即可。

#include <cstdio>
#include <iostream>
#include <cctype>
#include <cmath>
#include <algorithm>
#include <vector>
#include <bitset>
using namespace std;
#define F(i,a,b) for (int i=(a);i<=(b);i++)
#define X first
#define Y second
const int N=50005;
const int B=250;
const int RNF=-(~0u>>1);
const int INF=~0u>>1;
int online;
int n; pair<int,int> p[N];
int hx[N],hy[N];
int c,tot;
vector< pair<int,int> > vec[N];
struct BIT {
    pair<int,int> p[N];
    bitset<N> bit[B];
    void Init(void) {
        sort(p+1,p+n+1);
        F(i,1,n) F(j,(i+c-1)/c,tot)
            bit[j][p[i].Y]=1;
    }
    bitset<N> Get(int x) {
        bitset<N> ret;
        int loc=lower_bound(p+1,p+n+1,make_pair(x,INF))-p-1;
        if (!loc) return ret.reset(),ret;
        int b=(loc+c-1)/c; ret=bit[b-1]; F(i,(b-1)*c+1,loc) ret[p[i].Y]=1;
        return ret;
    }
    bitset<N> Query(int l,int r) {
        return Get(r)^Get(l-1);
    }
}g[4];
int m;
inline int rd(void) {
    int x=0,f=1; char c=getchar();
    for (;!isdigit(c);c=getchar()) if (c=='-') f=-1;
    for (;isdigit(c);c=getchar()) x=x*10+c-'0';
    return x*f;
}
inline void decode(int &x1,int &y1,int &x2,int &y2,int ansx,int ansy) {
    x1+=online*(ansx+ansy); y1+=online*(ansx+ansy); x2+=online*(ansx+ansy); y2+=online*(ansx+ansy);
    x1=lower_bound(hx+1,hx+n+1,x1)-hx;
    y1=lower_bound(hy+1,hy+n+1,y1)-hy;
    x2=upper_bound(hx+1,hx+n+1,x2)-hx-1;
    y2=upper_bound(hy+1,hy+n+1,y2)-hy-1;
}
int main(void) {
    #ifndef ONLINE_JUDGE
        freopen("sdchr.in","r",stdin);
        freopen("sdchr.out","w",stdout);
    #endif
    cin>>online;
    cin>>n; F(i,1,n) p[i].X=rd(),p[i].Y=rd();
    F(i,1,n) hx[i]=p[i].X; sort(hx+1,hx+n+1); F(i,1,n) p[i].X=lower_bound(hx+1,hx+n+1,p[i].X)-hx;
    F(i,1,n) hy[i]=p[i].Y; sort(hy+1,hy+n+1); F(i,1,n) p[i].Y=lower_bound(hy+1,hy+n+1,p[i].Y)-hy;
    c=(int)sqrt(n); tot=(n+c-1)/c;
    F(i,1,n) g[0].p[i]=make_pair(p[i].X,i),g[1].p[i]=make_pair(p[i].Y,i);
    g[0].Init(); g[1].Init();
    int ind=0;
    F(i,1,n) vec[p[i].X].push_back(make_pair(p[i].Y,i));
    F(i,1,n) if (vec[i].size()>0) {
        sort(vec[i].begin(),vec[i].end());
        F(j,0,vec[i].size()-1)
            g[2].p[++ind]=make_pair(j>0?vec[i][j-1].X:0,vec[i][j].Y);
        vec[i].clear();
    }
    g[2].Init();
    ind=0;
    F(i,1,n) vec[p[i].Y].push_back(make_pair(p[i].X,i));
    F(i,1,n) if (vec[i].size()>0) {
        sort(vec[i].begin(),vec[i].end());
        F(j,0,vec[i].size()-1)
            g[3].p[++ind]=make_pair(j>0?vec[i][j-1].X:0,vec[i][j].Y);
        vec[i].clear();
    }
    g[3].Init();
    int ansx=0,ansy=0; cin>>m;
    F(c,1,m) {
        int x1=rd(),y1=rd(),x2=rd(),y2=rd();
        decode(x1,y1,x2,y2,ansx,ansy);
        bitset<N> t=g[0].Query(x1,x2)&g[1].Query(y1,y2);
        ansx=(t&g[2].Get(y1-1)).count();
        ansy=(t&g[3].Get(x1-1)).count();
        printf("%d %d\n",ansx,ansy);
    }
    return 0;
}