ACWing 248. 窗内的星星|扫描线+懒惰标记

传送门

题目描述

在一个天空中有很多星星（看作平面直角坐标系），已知每颗星星的坐标和亮度（都是整数）。

求用宽为W、高为H的矩形窗户（W,H为正整数）能圈住的星星的亮度总和最大是多少。（矩形边界上的星星不算）

输入格式

输入包含多组测试用例。

每个用例的第一行包含3个整数：n，W，H，表示星星的数量，矩形窗口的宽和高。

然后是n行，每行有3个整数：x，y，c，表示每个星星的位置（x，y）和亮度。

没有两颗星星在同一点上。

输出格式

每个测试用例输出一个亮度总和最大值。

每个结果占一行。

数据范围

1≤n≤10000,
1≤W,H≤1000000,
10≤x,y<231

输入样例：

输出样例：

5

6

题意：求亮度总和。相当于求矩形面积并中各个重合区间出现的最大亮度和。

题解：https://www.cnblogs.com/l999q/p/11366840.html可参考这篇博客，不同点在于它是维护亮度和（相当于维护那篇博客中的最大cnt值）。

要注意的是：

题目中说矩形边界上的星星不算，那么我们线段的上边界要减一（存边界的四元组的时候处理）。
若一个矩形的右边界与另一个矩形的左边界重合时，先减去左边矩阵的亮度再加上右边矩阵的亮度。

代码：

#include <bits/stdc++.h>

using namespace std;

#define ll long long

const int N = 2e4 + ;

struct node{

    int x,y1,y2,val;

    node() {}

    node(int x, int y1, int y2,int val){

        this->x = x; this->val = val;

        this->y1 = y1; this->y2 = y2;

    }

    bool operator <(const node &t)const {

        return x<t.x;

    }

};

struct Tree{

    int l,r;

    int val,lazy;

}t[N<<];

vector<node> a;

vector<int> v;

void build(int rt,int l,int r) {

    t[rt].l = l,t[rt].r = r;

    t[rt].val = ; t[rt].lazy = ;

    if (l == r) return;

    int mid = (l+r)>>;

    build(rt<<,l,mid);

    build(rt<<|,mid+,r);

}

void update(int rt,int l,int r,int val) {

    if (l <= t[rt].l && r >= t[rt].r) {

        t[rt].val += val;

        t[rt].lazy += val;

        return;

    }

    if (t[rt].lazy) {

        t[rt<<].val += t[rt].lazy;

        t[rt<<].lazy += t[rt].lazy;

        t[rt<<|].val += t[rt].lazy;

        t[rt<<|].lazy += t[rt].lazy;

        t[rt].lazy = ;

    }

    int mid = (t[rt].l+t[rt].r)>>;

    if (l <= mid) update(rt<<,l,r,val);

    if (r > mid) update(rt<<|,l,r,val);

    t[rt].val = max(t[rt<<].val,t[rt<<|].val);

}

int main() {

    int n,w,h;

    while (~scanf("%d%d%d",&n,&w,&h) ) {

        v.clear();a.clear();

        for(int i = ; i < n; i++) {

            int x,y,c;

            scanf("%d%d%d",&x,&y,&c);

            v.push_back(y);

            v.push_back(y+h-);

            a.push_back(node(x,y,y+h-,c));

            a.push_back(node(x+w,y,y+h-,-c)); // y坐标边界要减，x坐标不要减

        }

        v.push_back(-);

        sort(a.begin(),a.end());

        sort(v.begin(),v.end());

        v.erase(unique(v.begin(),v.end()),v.end());

        n=v.size();

        build(,,n);

        int ans = ;

        for (int i = ; i < n; i++) {

            int l = lower_bound(v.begin(),v.end(),a[i].y1) - v.begin();

            int r = lower_bound(v.begin(),v.end(),a[i].y2) - v.begin();

            update(,l,r,a[i].val);

            if (a[i].val>) ans = max(ans,t[].val);

        }

        printf("%lld\n",ans);

    }

    return ;

}

巴特西