P10814 离线二维数点

离线二维数点：固定一个维度，维护另一个维度

问题

P10814 【模板】离线二维数点
给定序列 $a$，多次询问区间 $[l,r]$ 中满足 $a_i\le x$ 的元素个数。

数据规模：$n,m,a_i,l,r,x\le 2\times 10^6$。

把每个元素看成平面上的点 $(i,a_i)$，一次询问就是统计矩形 $[l, r] \times (-\infty, x]$ 中的点数。这是标准的离线二维数点模型：先按照一个维度排序扫描，使这一维的限制随着扫描进度自动满足，再用树状数组维护另一个维度。

1. 按值扫描

第一种做法是按值维护，从下往上扫描，将点 $(i,a_i)$ 按 $a_i$ 升序排序，将询问按 $x$ 升序排序。处理阈值为 $x$ 的询问时，把所有满足 $a_i\le x$ 的点加入树状数组，并在它们的位置 $i$ 上加一。

此时树状数组中恰好保存所有值不超过 $x$ 的位置，因此查询位置区间 $[l,r]$ 的和就是答案。

时间复杂度为 $O((n+m)\log(n+m))$，空间复杂度为 $O(n+m)$。

▶

P10814-1：按值扫描

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 l, r, x, idx;
} qs[maxn];

int a[maxn];
int ans[maxn];

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

    for( int i = 1; i <= n; ++ i ) {
        a[i] = read( );
        ps[i] = { i, a[i] };
    }

    for( int i = 1; i <= m; ++ i ) {
        qs[i].l = read( ), qs[i].r = read( );
        qs[i].x = read( ), qs[i].idx = i;
    }

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

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

    bit.init( n );
    int cur = 1;

    for( int i = 1; i <= m; ++ i ) {
        auto [ql, qr, qx, idx] = qs[i];
        while( cur <= n && ps[cur].y <= qx ) {
            bit.add( ps[cur].x, 1 );
            ++ cur;
        }
        ans[idx] = bit.ask( ql, qr );
    }

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

2. 交换扫描维度

也可以先把区间询问拆成两个位置前缀，比如说 $(l, r, x)$，可以拆解成 $F(r, x) - F(l-1, x)$。

其中 $F(p,x)$ 表示前缀 $[1,p]$ 中不大于 $x$ 的元素个数，在扫描的过程中记录前后两次查询，累加到对应的答案即可。

记前者为系数 $+1$ 的事件，后者为系数 $-1$ 的事件，同理用树状数组来维护即可。不过这里维护的值域，所以可能需要离散化处理。

这种做法和上面的基础做法完全对偶，只是交换了维护的维度而已。

▶

P10814：按位置扫描

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_leq_idx( 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 Event {
    int x, y, idx, opt;
} es[maxn << 1];

int a[maxn];
int ans[maxn];

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

    for( int i = 1; i <= n; ++ i ) {
        a[i] = read( );
        disc.add( a[i] );
    }
    disc.init( );

    int ecnt = 0;
    for( int i = 1; i <= m; ++ i ) {
        int l = read( ), r = read( ), x = read( );
        int rk = disc.get_leq_idx( x );
        es[++ ecnt] = { r, rk, i, 1 };
        es[++ ecnt] = { l - 1, rk, i, -1 };
    }

    sort( es + 1, es + ecnt + 1, []( Event A, Event B ) {
        return A.x < B.x;
    } );

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

    for( int i = 1; i <= ecnt; ++ i ) {
        auto [x, y, idx, opt] = es[i];
        while( cur < x ) {
            ++ cur;
            int idx = disc.get_idx( a[cur] );
            bit.add( idx, 1 );
        }
        ans[idx] += opt * bit.ask( y );
    }

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

记录

• 归属：树状数组、[[扫描线模型|扫描线]]、[[二维偏序]]
• 新增：离线二维数点的核心不是固定扫描哪一维，而是让一维限制随排序自动满足，并把另一维变成可维护的前缀计数；区间还可以先拆成两个位置前缀事件。
• 分类：待定