P2163 园丁的烦恼

园丁的烦恼：把矩形计数拆成二维前缀

问题

P2163 [SHOI2007] 园丁的烦恼
平面上给定若干个点，多次询问闭合矩形 $[a,c]\times[b,d]$ 内的点数；同一坐标可以有多个点。

数据规模：$n,m\le 5\times 10^5$，坐标不超过 $10^7$。

首先注意到这是一个二维数点问题，简单的做法就是二维前缀和，但是本题数据规模不支持，于是想到一道类似的题 P10814 离线二维数点，结合 [[二维前缀和]] 的容斥原理，我们可以轻松套用模型解出本题。

记二维前缀函数 $F(X, Y) = \mid \{ (x_{i}, y_{i}) \mid x_{i} \le X, y_{i} \le Y \} \mid$，那么矩形 $[a, c] \times [b, d]$ 中的点数就可以用容斥写成 $F(c, d) - F(a-1,d) - F(c,b-1) + F(a-1,b-1)$。

按 $X$ 排序事件，加入所有 $x_{i} \le X$ 的点，然后在树状数组上查询 $y_{i} \le Y$ 的点的数量。

排序复杂度为 $O((n+m)\log(n+m))$，树状数组操作复杂度为 $O((n+m)\log n)$，总空间复杂度为 $O(n+m)$。

▶

P2163

struct Disc {
/* ======================================== */
vector<int> v;
void clear( ) { v.clear( ); }
void add( int x ) { v.push_back( x ); }
void init( ) {
    sort( v.begin( ), v.end( ) );
    v.erase( unique( v.begin( ), v.end( ) ), v.end( ) );
}
int size( ) { return v.size( ); }
int get_idx( int x ) { return lower_bound( v.begin( ), v.end( ), x ) - v.begin( ) + 1; }
int get_rnk( int x ) { return upper_bound( v.begin( ), v.end( ), x ) - v.begin( ); }
int get_val( int idx ) { return v[idx - 1]; }
/* ======================================== */
} disc;

struct BIT {
/* ======================================== */
ll tr[maxn];
int sz;
void init( int N ) { sz = N;
    fill( tr, tr + sz + 2, 0 );
}
void add( int idx, ll val ) {
    for( int i = idx; i <= sz; i += i & -i ) tr[i] += val;
}
ll ask( int idx ) {
    ll res = 0;
    for( int i = idx; i; i -= i & -i ) res += tr[i];
    return res;
}
ll ask( int l, int r ) { return ask( r ) - ask( l - 1 ); }
/* ======================================== */
} bit;

struct Point {
    int x, y;
} ps[maxn];

struct Query {
    int x, y, idx, opt;
} qs[maxn * 4];

ll ans[maxn];

void solve( ) {
    int n = read( ), m = read( );

    disc.clear( );
    for( int i = 1; i <= n; ++ i ) {
        ps[i].x = read( ), ps[i].y = read( );
        disc.add( ps[i].y );
    }
    disc.init( );
    
    int qcnt = 0;
    for( int i = 1; i <= m; ++ i ) {
        int a = read( ), b = read( );
        int c = read( ), d = read( );
        qs[++ qcnt] = { c, d, i, 1 };
        qs[++ qcnt] = { a - 1, d, i, -1 };
        qs[++ qcnt] = { c, b - 1, i, -1 };
        qs[++ qcnt] = { a - 1, b - 1, i, 1 };
    }

    sort( ps + 1, ps + n + 1, []( Point A, Point B ) {
        return A.x < B.x;
    } );

    sort( qs + 1, qs + qcnt + 1, []( Query A, Query B ) {
        return A.x < B.x;
    } );

    bit.init( disc.size( ) );
    int cur = 1;

    for( int i = 1; i <= qcnt; ++ i ) {
        auto [x, y, idx, opt] = qs[i];
        while( cur <= n && ps[cur].x <= x ) {
            int pos = disc.get_idx( ps[cur].y );
            bit.add( pos, 1 );
            ++ cur;
        }
        int pos = disc.get_rnk( y );
        ans[idx] += 1ll * opt * bit.ask( pos );
    }

    for( int i = 1; i <= m; ++ i ) {
        cout << ans[i] << '\n';
    }
}

记录

• 归属：树状数组、[[扫描线模型|扫描线]]、[[二维偏序]]
• 新增：二维矩形计数可以先容斥为四个二维前缀，再固定一个维度的扫描顺序，把另一维压缩成树状数组前缀和。
• 分类：待定