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)); }