題目大意：
求一個窗體覆蓋最多的星星的權值。
思路分析：
每個星星看成
左下點為x y
右上點為x+w-1 y+h-1 的矩形。
然后求出最大覆蓋的和。
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#define lson num<<1,s,mid
#define rson num<<1|1,mid+1,e
#define maxn 10005
using namespace std;
typedef long long LL;
LL res[maxn<<4];
LL sum[maxn<<4];
LL x[maxn<<4];struct node
{LL s,e,h,type;bool operator < (const node &cmp)const{if(h==cmp.h)return type>cmp.type;return h<cmp.h;}
}scline[maxn<<1];void pushup(int num)
{sum[num]=max(sum[num<<1],sum[num<<1|1]);
}
void pushdown(int num)
{if(res[num]){sum[num<<1]+=res[num];sum[num<<1|1]+=res[num];res[num<<1]+=res[num];res[num<<1|1]+=res[num];res[num]=0;}
}
void build(int num,int s,int e)
{res[num]=0;sum[num]=0;if(s==e)return;int mid=(s+e)>>1;build(lson);build(rson);
}
void update(int num,int s,int e,int l,int r,LL val)
{if(l<=s && r>=e){res[num]+=val;sum[num]+=val;return;}int mid=(s+e)>>1;pushdown(num);if(l<=mid)update(lson,l,r,val);if(r>mid)update(rson,l,r,val);pushup(num);
}
int main()
{LL n,w,h;while(cin>>n>>w>>h){for(int i=1;i<=n;i++){LL ts,te,tt;cin>>ts>>te>>tt;scline[i*2-1].s=ts,scline[i*2-1].e=ts+w-1,scline[i*2-1].h=te,scline[i*2-1].type=tt;scline[i*2].s=ts,scline[i*2].e=ts+w-1,scline[i*2].h=te+h-1,scline[i*2].type=-tt;x[i*2-1]=ts,x[i*2]=ts+w-1;}sort(scline+1,scline+1+n*2);sort(x+1,x+1+n*2);int m=unique(x+1,x+1+n*2)-x;build(1,1,m);LL ans=0;for(int i=1;i<=n*2;i++){int l=lower_bound(x+1,x+m,scline[i].s)-x;int r=lower_bound(x+1,x+m,scline[i].e)-x;update(1,1,m,l,r,scline[i].type);ans=max(ans,sum[1]);}cout<<ans<<endl;}return 0;
}
/*
2 1 5
0 0 100
0 4 101
*/
轉載于:https://www.cnblogs.com/wzjhoutai/p/7353371.html
總結
以上是生活随笔為你收集整理的poj 2482 Stars in Your Window （线段树扫描线）的全部內容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。
