P1502 窗口的星星

窗口的星星：把选窗口转化为带权矩形覆盖最大值

问题

P1502 窗口的星星
平面上有若干颗带亮度的星星，选择一个宽为 $W$、高为 $H$ 的开窗口，求窗口内部星星的最大亮度和。

数据规模：$T\le 10$，每组 $n\le 10^4$，坐标小于 $2^{31}$。

看起来像一个二维滑动窗口问题，如果考虑移动窗口的话，考虑到这个坐标的值域，显然暴力的做法是不可行的。

反过来考虑一颗星星会对哪些窗口位置产生贡献。用 $(X,Y)$ 表示窗口右上角，星星 $(x_i,y_i)$ 位于窗口内部，当且仅当 $x_i < X < x_i+W, y_i < Y < y_i + H$。

也就是说，每颗亮度为 $l_{i}$ 的星星都会在 $(x_{i}, x_{i} + W) \times (y_{i}, y_{i} + H)$ 这一块矩形中产生贡献，只要选择的右上角点 $(X, Y)$ 落在这个矩形内，就能获得 $l_{i}$ 的贡献。

原问题于是转化为：求平面上被若干带权矩形覆盖时，某一点能取到的最大权值和，然后实现原理详见 P5490 矩形面积并 一文。

下面解释本题的线段树，由于是最大权值和，而且有区间修改，所以本题需要用到懒标记，简单的写一下带区间修改 + 区间最值的线段树。

扫描横坐标时，每进入一颗星星的贡献矩形，就对对应的纵坐标区间整体加上 $l_{i}$​；离开时整体减去 $l_{i}$​。因此，线段树叶子上的值就表示：选择相应纵坐标时能够获得的亮度总和，节点维护范围内的最大值。根节点的 mx 就是当前横坐标下能够取得的最大星星亮度和。

题目不统计窗口边框上的星星。代码把贡献区间按半开区间维护，并将同一横坐标上的加入、删除事件全部处理完后再查询，相当于考察刚越过该事件坐标后的状态：到期贡献已经删除，新贡献已经加入，从而避免事件先后顺序破坏开边界。

▶

P1502

struct Disc {
/* ======================================== */
vector<ll> v;
void clear( ) { v.clear( ); }
void add( ll 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( ll x ) { return lower_bound( v.begin( ), v.end( ), x ) - v.begin( ) + 1; }
ll get_val( int idx ) { return v[idx - 1]; }
/* ======================================== */
} disc;

#define ls ( u << 1 )
#define rs ( u << 1 | 1 )

struct SegTree {
/* ======================================== */
struct Node {
    int l, r;
    ll mx, add;
} tr[maxn << 2];

void push_up( int u ) {
    tr[u].mx = max( tr[ls].mx, tr[rs].mx );
}

void apply( int u, ll val ) {
    tr[u].mx += val;
    tr[u].add += val;
}

void push_down( int u ) {
    if( !tr[u].add ) return;
    apply( ls, tr[u].add );
    apply( rs, tr[u].add );
    tr[u].add = 0;
}

void build( int u, int l, int r ) {
    tr[u] = { l, r, 0, 0 };
    if( l == r ) return ;
    int mid = ( l + r ) >> 1;
    build( ls, l, mid );
    build( rs, mid + 1, r );
}

void upd( int u, int l, int r, ll val ) {
    if( l <= tr[u].l && tr[u].r <= r ) { 
        apply( u, val );
        return ;
    }
    push_down( u );
    int mid = ( tr[u].l + tr[u].r ) >> 1;
    if( l <= mid ) upd( ls, l, r, val );
    if( mid < r ) upd( rs, l, r, val );
    push_up( u );
}

ll ask( ) { return tr[1].mx; }
/* ======================================== */
} seg;

struct Event {
    ll x, y1, y2, tag;
    bool operator < ( const Event &oth ) const { return x < oth.x; }
};

vector<Event> events;

void solve( ) {
    int n = read( );
    ll W = read( ), H = read( );

    disc.clear( );
    events.clear( );
    events.reserve( n << 1 );

    for( int i = 1; i <= n; ++ i ) {
        ll xi = read( ), yi = read( );
        ll li = read( );
        events.push_back({ xi, yi, yi + H, li });
        events.push_back({ xi + W, yi, yi + H, -li });
        disc.add( yi );
        disc.add( yi + H );
    }

    disc.init( );
    sort( events.begin( ), events.end( ) );

    int m = disc.size( );
    seg.build( 1, 1, m - 1 );

    ll ans = 0;
    int ecnt = events.size( );

    for( int l = 0; l < ecnt; ) {
        int r = l;
        while( r < ecnt && events[r].x == events[l].x ) {
            int ql = disc.get_idx( events[r].y1 );
            int qr = disc.get_idx( events[r].y2 );
            seg.upd( 1, ql, qr - 1, events[r].tag );
            ++ r;
        }
        ans = max( ans, seg.ask( ) );
        l = r;
    }
    cout << ans << '\n';
}

int main( ) {
    int T = read( );
    while( T -- ) solve( );
    return 0;
}

记录

• 归属：[[扫描线模型|扫描线]]、方法/坐标变换

• 新增：固定大小窗口的最优放置可以反向表示为“每个点对窗口锚点贡献一个带权矩形”，再求带权矩形覆盖最大值；开边界通过同坐标事件分组和半开区间处理。

• 分类：待定