二维线段树洛谷P3437 [POI2006]TET-Tetris 3D

2019-11-08 03:27:54

字体：大中小

来源：转载

供稿：网友

https://www.luogu.org/PRoblem/show?pid=3437 代码就不用看了，全抄hzwer的，但是我调了一个多钟头汗；这个就是基本的二维线段树了，lazy都不用的，不知道是不是传说中的标记永久化；二维线段树，我选择树套树，因为四分树好像会被卡 ~~网上只有书树套树的标程~~ 二维线段树，无论是什么操作都十分繁琐吧；所以我们要精简； maketree这种东西能不搞就不弄把，只要在函数参数里多加l,r表示当前区间的范围就好了呀；怎么搞呢，其实和一维的线段树差不多，基本上一样把；当然了，洛谷的内存是128M，这个就坑爹了；因为最多有1000个点，线段树最坏是满二叉树； 2^10=1024>1000;所以我们开1024*2=2048的就好了；

#include<iostream>#include<cstdio>using namespace std;int D,S,n,d,s,h,x,y,qs,qx,qz,qy;struct treex{ int vv[2048],tag[2048]; int outit(int l,int r,int x,int y,int num){ if(x<=l&&r<=y)return vv[num]; int ans=tag[num],mid=(l+r)>>1; if(x<=mid )ans=max(ans,outit(l,mid ,x,y,num<<1 )); if(y>=mid+1)ans=max(ans,outit(mid+1,r,x,y,num<<1|1)); return ans; } void change(int l,int r,int x,int y,int num,int val){ vv[num]=max(vv[num],val); if(x<=l&&r<=y){tag[num]=max(tag[num],val);return;} int mid=(l+r)>>1; if(x<=mid )change(l,mid ,x,y,num<<1 ,val); if(y>=mid+1)change(mid+1,r,x,y,num<<1|1,val); }};struct treey{ treex tag[2048],vv[2048]; int outit(int l,int r,int x,int y,int num){ if(x<=l&&r<=y)return vv[num].outit(1,S,qx,qs,1); int ans=tag[num].outit(1,S,qx,qs,1),mid=(l+r)>>1; if(x<=mid )ans=max(ans,outit(l,mid ,x,y,num<<1 )); if(y>=mid+1)ans=max(ans,outit(mid+1,r,x,y,num<<1|1)); return ans; } void change(int l,int r,int x,int y,int num,int val){ vv[num].change(1,S,qx,qs,1,val); if(x<=l&&r<=y){tag[num].change(1,S,qx,qs,1,val);return;} int mid=(l+r)>>1; if(x<=mid )change(l,mid ,x,y,num<<1 ,val); if(y>=mid+1)change(mid+1,r,x,y,num<<1|1,val); }}T;int main(){ scanf("%d%d%d",&D,&S,&n); while(n--){ scanf("%d%d%d%d%d",&d,&s,&h,&x,&y); qx=y+1;qz=x+1;qs=y+s;qy=x+d;// cout<<qz<<' '<<qy<<' '<<qx<<' '<<qs<<endl; int ans=T.outit(1,D,qz,qy,1); T.change(1,D,qz,qy,1,ans+h); qx=1;qs=S;// cout<<T.outit(1,D,1,D,1)<<endl; } qx=1;qs=S; printf("%d",T.outit(1,D,1,D,1));}

上一篇：33. Search in Rotated Sorted Array

下一篇：POJ2388 Who's in the Middle