首页 > 代码库 > 【POJ2482】Stars in Your Window(线段树,扫描线)
【POJ2482】Stars in Your Window(线段树,扫描线)
题意:在二维坐标系中有一些带权值的点,要求用一个长宽指定不能互换的框套住其中的一些,使得它们的权值和最大。
n<=10000 x,y<=2^31
思路:首先按X排序,将Y坐标离散化,X坐标用扫描线框定,每个点(x,y)在x中只对y有a[i]的贡献,y+h有-a[i]的贡献,线段树(树状数组更好写)维护最大子段和即可。
1 var t:array[1..200000]of record 2 l,r,s,m:int64; 3 end; 4 x,y,c,a,h:array[1..50000]of int64; 5 n,m,i,j,tt,ww,up,w1,h1:longint; 6 ans:int64; 7 8 procedure swap(var x,y:int64); 9 var t:int64; 10 begin 11 t:=x; x:=y; y:=t; 12 end; 13 14 procedure qsort(l,r:longint); 15 var i,j,mid1,mid2:longint; 16 begin 17 i:=l; j:=r; mid1:=x[(l+r)>>1]; mid2:=y[(l+r)>>1]; 18 repeat 19 while (mid1>x[i])or((mid1=x[i])and(mid2>y[i])) do inc(i); 20 while (mid1<x[j])or((mid1=x[j])and(mid2<y[j])) do dec(j); 21 if i<=j then 22 begin 23 swap(x[i],x[j]); 24 swap(y[i],y[j]); 25 swap(a[i],a[j]); 26 inc(i); dec(j); 27 end; 28 until i>j; 29 if l<j then qsort(l,j); 30 if i<r then qsort(i,r); 31 end; 32 33 procedure qsort2(l,r:longint); 34 var i,j:longint; 35 mid:int64; 36 begin 37 i:=l; j:=r; mid:=c[(l+r)>>1]; 38 repeat 39 while mid>c[i] do inc(i); 40 while mid<c[j] do dec(j); 41 if i<=j then 42 begin 43 swap(c[i],c[j]); 44 inc(i); dec(j); 45 end; 46 until i>j; 47 if l<j then qsort2(l,j); 48 if i<r then qsort2(i,r); 49 end; 50 51 function max(x,y:int64):int64; 52 begin 53 if x>y then exit(x); 54 exit(y); 55 end; 56 57 procedure pushup(p:longint); 58 var ls,rs:longint; 59 begin 60 ls:=p<<1; rs:=ls+1; 61 t[p].l:=max(t[ls].l,t[ls].s+t[rs].l); 62 t[p].r:=max(t[rs].r,t[rs].s+t[ls].r); 63 t[p].m:=max(t[ls].r+t[rs].l,max(t[ls].m,t[rs].m)); 64 end; 65 66 procedure update(l,r,x,v,p:longint); 67 var mid:longint; 68 begin 69 if l=r then 70 begin 71 t[p].s:=t[p].s+v; 72 t[p].l:=t[p].s; t[p].r:=t[p].s; t[p].m:=t[p].s; 73 exit; 74 end; 75 mid:=(l+r)>>1; 76 if x<=mid then update(l,mid,x,v,p<<1) 77 else update(mid+1,r,x,v,p<<1+1); 78 t[p].s:=t[p].s+v; 79 pushup(p); 80 end; 81 82 function hash(x:int64):longint; 83 var l,r,mid,last:longint; 84 begin 85 l:=1; r:=up; last:=1; 86 while l<=r do 87 begin 88 mid:=(l+r)>>1; 89 if x=h[mid] then begin last:=mid; r:=mid-1; end; 90 if x<h[mid] then r:=mid-1; 91 if x>h[mid] then l:=mid+1; 92 end; 93 exit(last); 94 end; 95 96 begin 97 assign(input,‘poj2482.in‘); reset(input); 98 assign(output,‘poj2482.out‘); rewrite(output); 99 while not eof do 100 begin 101 readln(n,w1,h1); 102 if n=0 then break; 103 for i:=1 to n do read(x[i],y[i],a[i]); 104 qsort(1,n); 105 m:=0; 106 for i:=1 to n do 107 begin 108 inc(m); c[m]:=y[i]; 109 inc(m); c[m]:=y[i]+h1; 110 end; 111 qsort2(1,m); 112 up:=1; h[1]:=c[1]; 113 for i:=2 to m do 114 if c[i]>c[i-1] then 115 begin 116 if c[i]=c[i-1]+1 then begin inc(up); h[up]:=c[i]; end 117 else 118 begin 119 inc(up); h[up]:=c[i-1]; 120 inc(up); h[up]:=c[i]; 121 end; 122 end; 123 ans:=-maxlongint; 124 tt:=1; ww:=0; 125 while ww<n do 126 begin 127 inc(ww); 128 while (tt<=n)and(x[tt]+w1-1<x[ww]) do 129 begin 130 update(1,up,hash(y[tt]),-a[tt],1); 131 update(1,up,hash(y[tt]+h1),a[tt],1); 132 inc(tt); 133 end; 134 update(1,up,hash(y[ww]),a[ww],1); 135 update(1,up,hash(y[ww]+h1),-a[ww],1); 136 ans:=max(ans,t[1].m); 137 end; 138 writeln(ans); 139 for i:=1 to up<<2 do 140 begin 141 t[i].s:=0; t[i].l:=0; t[i].r:=0; t[i].m:=0; 142 end; 143 end; 144 close(input); 145 close(output); 146 end.
【POJ2482】Stars in Your Window(线段树,扫描线)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。