AcWing 248. 窗内的星星    原题链接    困难

作者： 作者的头像   秦淮岸灯火阑珊 ,  2019-02-15 21:10:04 ,  所有人可见 ,  阅读 3050

18


6

原题链接
更好的阅读体验

题目描述

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

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

输入格式
输入包含多组测试用例。

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

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

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

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

每个结果占一行。

数据范围
$1≤n≤10000$
$1≤W,H≤1000000$
$0≤x,y<2^{31}$

样例

输入样例：
3 5 4
1 2 3
2 3 2
6 3 1
3 5 4
1 2 3
2 3 2
5 3 1
输出样例：
5
6

线段树+扫描线+离散化+二分

离散化:坐标大就离散化,每次都是这样,差评
二分:离散化就二分,每次都是这样,差评
扫描线:数据范围大,又是二维,还是要扫描线.每次都是这样,差评
线段树:数据范围大,区间可加性,一堆区间操作,还是要线段树.每次都是这样,差评
首先将问题转化为:平面上由若干个区域,每个区域都带有一个权值,求在哪个坐标上重叠的区域权值和最大.记住,每一个区域都是有一个星星产生的,权值等于星星的亮度.
左上角,左下角,右上角,右下角可以由四元组保存$(x,y,y+h-1,c)$和$(x+w,y,y+h-1,-c)$然后按照横坐标第一位的值排序即可.四元组要分开看.$(x,y,c)$$(x,y+h-1,c)$和$(x+w,y)$$(x+w,y+h-1,-c)$

C++ 代码

#include <bits/stdc++.h>
using namespace std;
const int N=2e4+10;//要2*n,切记切记,我就是因为这个恶心的锅,坑害了一个半小时.
#define int long long//注意
#define lson l,(l+r)/2,p<<1
#define rson (l+r)/2,r,p<<1|1
int n,w,h,ys[N];
struct line_tree
{
    int l,r,len,lazy;//开了懒惰标记,也就是延迟标记
    #define l(x) x<<1
    #define r(x) (x<<1)+1
    #define m(x) (t[x].l+t[x].r)>>1
} t[N<<2];
struct node
{
    int x,y1,y2,f;
} p[N];
int cmp(node a,node b)
{
    return a.x<b.x || (a.x==b.x && a.f<0);//排序特殊点
}
inline void push_up(int p)
{
    t[p].len=max(t[l(p)].len,t[r(p)].len)+t[p].lazy;
}
inline void build(int l,int r,int p)
{
    t[p].l=ys[l];
    t[p].r=ys[r];
    t[p].lazy=0;
    t[p].len=0;
    if (r-l==1)
        return ;
    int mid=(l+r)>>1;
    build(lson);
    build(rson);
    push_up(p);
}
inline void change(int l,int r,int k,int p)
{
    if (t[p].l>=l && t[p].r<=r)
    {
        t[p].lazy+=k;
        t[p].len+=k;
        return ;
    }
    if (l<t[l(p)].r)
        change(l,min(r,t[l(p)].r),k,l(p));
    if (r>t[r(p)].l)
        change(max(l,t[r(p)].l),r,k,r(p));
    push_up(p);
}
inline void init()
{
    while(scanf("%lld%lld%lld",&n,&w,&h)!=EOF)
    {
        int cnt=0,num=1;
        for(int i=1; i<=n; i++)
        {
            int xx,yy,k;
            scanf("%lld%lld%lld",&xx,&yy,&k) ;
            p[cnt].x=xx;
            p[cnt].y1=yy;
            p[cnt].y2=yy+h;
            p[cnt++].f=k;

            p[cnt].x=xx+w;
            p[cnt].y1=yy;
            p[cnt].y2=yy+h;
            p[cnt++].f=-k;

            ys[num++]=yy;
            ys[num++]=yy+h;
        }
        sort(ys+1,ys+num);
        int ans=0;
        num=unique(ys+1,ys+num)-(ys+1);
        sort(p,p+cnt,cmp);
        build(1,num,1);
        for(int i=0; i<cnt; i++)
        {
            change(p[i].y1,p[i].y2,p[i].f,1);
            if(p[i].f>0)
                ans=max(ans,t[1].len);
        }
        printf("%lld\n",ans);
    }
}
signed main()
{
//  freopen("stdin.in","r",stdin);
//  freopen("stdout.out","w",stdout);
    init();
    return 0;
}

30 评论

用户头像
爱玩CF的帅小伙   2023-02-19 10:01         踩      回复

dalao，可以帮忙看看错在哪里么，只有一个数据过不去

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
const int N = 1e4 + 10;
typedef long long ll;
struct edge {
    int x, y1;
    ll y2;
    int k;
    bool operator< (const edge& t) const {
        return x < t.x;
    }
} edges[N * 2];

struct treeNode {
    int l, r;
    ll dat, add;
} tr[N * 8];

vector<ll> alls;
void init() {
    sort(alls.begin(), alls.end());
    alls.erase(unique(alls.begin(), alls.end()), alls.end());
}
int serch(ll x) {
    int l = 0, r = alls.size() - 1;
    while(l < r) {
        int mid = l + r >> 1;
        if(alls[mid] >= x) r = mid;
        else l = mid + 1;
    }
    return l + 1;
}

void pushup(int u) {
    tr[u].dat = max(tr[u << 1].dat, tr[u << 1 | 1].dat);
}

void pushdown(int u) {
    int l = u << 1, r = u << 1 | 1;
    if(tr[u].add) {
        tr[l].dat += tr[u].add;
        tr[r].dat += tr[u].add;
        tr[l].add += tr[u].add;
        tr[r].add += tr[u].add;
        tr[u].add = 0;
    }

}

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

void change(int u, int l, int r, int k) {
    if(l <= tr[u].l && r >= tr[u].r) {
        tr[u].dat += k;
        tr[u].add += k;
        return;
    }
    pushdown(u);
    int mid = tr[u].l + tr[u].r >> 1;
    if(l <= mid) change(u << 1, l, r, k);
    if(r > mid) change(u << 1 | 1, l, r, k);
    pushup(u);
}

int main() {
    int n, w, h;
    while(cin >> n >> w >> h) {
        int x, y, c;
        int j = 1;
        alls.clear();
        for(int i = 1; i <= n; ++i) {
            scanf("%d%d%d", &x, &y, &c);
            ll t = y + h - 1;
            edges[j++] = {x, y, t, c};
            edges[j++] = {x + w, y, t, -c};
            alls.push_back(y), alls.push_back(t);
        }
        init();
        sort(edges + 1, edges + j);
        ll ans = 0;
        build(1, 1, alls.size());
        for(int i = 1; i < j; ++i) {
            //cout << edges[i].x << ' '<< edges[i].y1 << ' ' << edges[i].y2 << ' ';
            change(1, serch(edges[i].y1), serch(edges[i].y2), edges[i].k);/*
            for(int i = 1; i <= 2; ++i) 
                cout << tr[1].dat << endl;*/
            ans = max(ans, tr[1].dat);
            //cout << ans << endl;
        }
        cout << ans << endl;
    }
}
用户头像
Link_Cut_Y   2021-10-01 16:40         踩      回复

只是将您的ys 改成了 vector<int> pos

用户头像
Link_Cut_Y   2021-10-01 16:40         踩      回复

dalao 可以帮忙看看错在哪里吗？？

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <vector>
#define int long long

using namespace std;

const int N = 2e4 + 10;
typedef long long LL;

int n, w, h;
vector<int> pos;

struct Seg
{
    int l, r, len, lazy;
}tr[N << 2];

struct node
{
    int x, y1, y2, f;
}p[N];

int cmp(node a, node b)
{
    return a.x < b.x || (a.x == b.x && a.f < 0);
}

void pushup(int u)
{
    tr[u].len = max(tr[u << 1].len, tr[u << 1 | 1].len) + tr[u].lazy;
}

void build(int u, int l, int r)
{
    tr[u] = {l, r, 0, 0};

    if (r - l == 1) return;

    int mid = (l + r) >> 1;
    build(u << 1, l, mid);
    build(u << 1 | 1, mid + 1, r);

    pushup(u);
}

void modify(int u, int l, int r, int k)
{
    if (tr[u].l >= l && tr[u].r <= r)
    {
        tr[u].lazy += k;
        tr[u].len += k;
        return;
    }

    if (l < tr[u << 1].r) modify(u << 1, l, min(r, tr[u << 1].r), k);
    if (r > tr[u << 1 | 1].l) modify(u << 1 | 1, max(l, tr[u << 1 | 1].l), r, k);

    pushup(u);
}

signed main()
{
    while (scanf("%lld%lld%lld", &n, &w, &h) != EOF)
    {
        int cnt = 0;
        for (int i = 1; i <= n; i ++ )
        {
            int a, b, c;
            scanf("%lld%lld%lld", &a, &b, &c);
            p[cnt] = {a, b, b + h, c};
            cnt ++ ;
            p[cnt] = {a + w, b, b + h, -c};
            cnt ++ ;

            pos.push_back(b);
            pos.push_back(b + h);
        }

        sort(pos.begin(), pos.end());
        int num = unique(pos.begin(), pos.end()) - pos.begin();

        sort(p, p + cnt, cmp);
        build(1, 1, num);

        int ans = 0;

        for (int i = 0; i < cnt; i ++ )
        {
            modify(1, p[i].y1, p[i].y2, p[i].f);
            if (p[i].f > 0) ans = max(ans, tr[1].len);
        }

        cout << ans << endl;
    }

    return 0;
}
用户头像
我是球球   2022-08-16 09:05         踩      回复

你是不是没有清空啊。。。@lcy

用户头像
Link_Cut_Y   2021-10-01 16:25         踩      回复

dalao 也用 define int long long 这样的 “偷奸耍滑” 吗qwq（逃

用户头像
lianziyu   2021-03-04 16:39         踩      回复

为什么存的是y+h？书上写的是y+h-1,而且也是能过的

用户头像
追风男孩   2020-01-30 20:56         踩      回复

矩形如果反过来的话，高和宽互换的话不会对结果产生影响吗

用户头像
songhn   2019-08-18 21:42         踩      回复

请问一下题解中将星星造成贡献的范围表示成一个矩形 也就是说将矩形中的每一个点作为窗户右上顶点都可以看见该星星 然后既然矩形边界上星星不算的话为什么产生贡献的矩阵是(x,y,y+h−1,c)和(x+w,y,y+h−1,−c)而不是(x+1,y+1,y+h−1,c)和(x+w-1,y+1,y+h−1,−c)，假如(x,y)是矩形右上顶点的话那么(x,y)上的星星应该不能被看见把

用户头像
秦淮岸灯火阑珊   2019-08-19 07:13         踩      回复

我们发现其实根据激光炸弹那道题目，我们就发现了。
不在矩阵边界，其实可以形象地将点偏移一下。
本来是$(x,y)$，然后我们把它变成$(x+0.5,t+0.5)$
其实这个和这个差不多的。
而且我们不是离散化了吗？

用户头像
songhn   2019-08-19 17:29    回复了 秦淮岸灯火阑珊 的评论         踩      回复

请问一下 样例中第二个答案是6也就是三个星星都能框进去 而数据是这样的:
3 5 4
1 2 3
2 3 2
5 3 1
最左边的点是(1,2)最右边的点是(5,3)
那么想要把这两个同时框进去不是需要至少宽度是6嘛也就是从0框到6
可样例中宽度是5 那么应该会有一个点卡在边界上那么不就不能算是有贡献了嘛

用户头像
秦淮岸灯火阑珊   2019-08-19 19:56    回复了 songhn 的评论         踩      回复

这么恐怖吗？好像的确如此啊。。。。
待会y总下课，我去问问y总。
是不是我们都理解错误了。
还是题目出锅了啊。

用户头像
秦淮岸灯火阑珊   2019-08-19 19:56    回复了 songhn 的评论         踩      回复

确认过眼神，是大佬的眼神。

用户头像
songhn   2019-08-23 20:17    回复了 秦淮岸灯火阑珊 的评论         踩      回复

您怎么说 是不是我理解错题意惹 @秦淮岸灯火阑珊

用户头像
秦淮岸灯火阑珊   2019-08-23 20:24    回复了 songhn 的评论         踩      回复

或者说是，我们都理解错误啦？
我也不知道啊，我去问问？

用户头像
yxc   2019-08-23 20:50    回复了 songhn 的评论         踩      回复

从0.5到5.5的框就可以啦，所以宽度是5的话可以同时包含(1, 2)和(5, 3)

用户头像
秦淮岸灯火阑珊   2019-08-23 20:51    回复了 yxc 的评论         踩      回复

哇，好棒啊。然后@songhn

用户头像
songhn   2019-08-23 21:09    回复了 秦淮岸灯火阑珊 的评论         踩      回复

好的 感谢 我在这卡了半天…

用户头像
OOOVOOO   2019-09-11 22:58    回复了 songhn 的评论         踩      回复

这里我也没搞懂 感觉书上给的(x, y, y + h - 1, c) 与 (x + w, y, y + h - 1, -c) 矩阵 四个点都不可以取啊，这里没有想出来，求大佬%%%

用户头像
songhn   2019-09-12 00:23    回复了 OOOVOOO 的评论         踩      回复

它只是要求星星在整点上 但是我框的矩形顶点是不用在整点上的 所以我们可以平移0.5这样就能多框一段了

用户头像
秦淮岸灯火阑珊   2019-09-12 17:35    回复了 songhn 的评论         踩      回复

您所言极是.

用户头像
Mintind   2019-08-11 17:53         踩      回复

return a.x<b.x || (a.x==b.x && a.f<0);
这意思是先减后增吗？ 为什么

用户头像
秦淮岸灯火阑珊   2019-08-11 18:32         踩      回复

没有啊。按照从小到大排序，如果相同就看a.f的关系。

用户头像
Mintind   2019-08-11 18:42    回复了 秦淮岸灯火阑珊 的评论         踩      回复

不是 我的意思是x相同的时候 先把要减的边减掉 再加要加的边 是吗

用户头像
Mintind   2019-08-11 18:44    回复了 Mintind 的评论         踩      回复

是因为存的是x和x+w而不是x和x+w-1吗

用户头像
秦淮岸灯火阑珊   2019-08-19 19:58    回复了 Mintind 的评论         踩      回复

似乎是的，但是这道题目目前有点问题呢。
这种评论下的评论，我似乎接受不到。
下回艾特一下我吧。
就是

@[你的名字]
用户头像
piiiiig   2019-03-23 09:25         踩      回复

为什么这个代码再电脑上运行就会显示invaild operator<，然后就运行不了。而在acwing上提交就会ac

用户头像
秦淮岸灯火阑珊   2019-03-23 17:56         踩      回复

电脑是运行没有问题,我是Dev-C++4.8.1

用户头像
秦淮岸灯火阑珊   2019-03-23 17:56         踩      回复

你的编译器是VS吗?VS我没有用过,不知道?

用户头像
piiiiig   2019-03-24 15:10    回复了 秦淮岸灯火阑珊 的评论         踩      回复

我的编译器是vs2013

用户头像
秦淮岸灯火阑珊   2019-03-24 15:56    回复了 piiiiig 的评论         踩      回复

VS我没有用过,不清楚,不过这个CE错误是重载失败,你看看是不是你的运行内存的锅?因为我这个代码唯一涉及到运行内存的,就只有宏定义.