首页 > 代码库 > poj 2482 Stars in Your Window (线段树扫描线)
poj 2482 Stars in Your Window (线段树扫描线)
题目大意:
求一个窗口覆盖最多的星星的权值。
思路分析:
每一个星星看成
左下点为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 */
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。