学了一些比较nb的操作 比如 可持久化树的区间修改 必须要标记可持久化...当然还有线段树套线段树 再有就是二维线段树了。
二维线段树 是这样的 每个节点都维护4个值 l r u d 也就是一个矩形 l r 表示从左到右区间范围 u d 表示从上到下的区间范围。
然后子节点每次都 分割四分之一 l r 之间取mid u d 之间取mid 然后一个大的矩阵就被我们分成4个小矩阵了。
考虑 这个矩阵是有点问题的 当奇数行或奇数列的时候我们不难发现 到最后一定是只有1 行 或者只有一列 这种情况就导致4个儿子之中可能几个儿子是没有值得也就是说他们的范围是不存在的但是 注意左上角的矩阵是永远存在的 这是这个矩阵的所在点的位置 不可能为空。
考虑如何 修改 之间修改就好啦 怎么查询 直接查询就好了 怎么下传标记 直接下传就好了。但是在做这几步的时候我们必须要严格的来询问 到底我们将要访问到的儿子是否为空 以免造成不必要的麻烦。
考虑儿子的节点标号如何 搞 可以直接动态开点的对吧 当然也有一种标号方式 zs = (p<<2)+1 zx =(p<<2)+2.。。等等注意这里我们根节点的编号为0 以免造成不必要的空间越界和更多的空间浪费。
当然标记永久化也是支持的 不过不太想写。
考虑复杂度的问题吧 建树的时间复杂度：大致估计 nm 空间复杂度也是这个
一次单点修改/区间修改/单点查询/区间查询的复杂度为 log(nm)
还算比较优秀 当然n m 是这个矩阵的大小n m 过大空间时间双双爆炸...
这道题 是二维线段树的裸题 设计到区间查询max 区间修改 当然可以利用树套树来写 不过我现在不太会。
好像这种开线段树的方式非常奇特 上面说的区间查询和区间修改复杂度 不太准确 这样写线段树做这道题的话有点吃力不过卡常能过。
//#include<bits/stdc++.h> #include<iostream> #include<iomanip> #include<ctime> #include<cstring> #include<string> #include<ctime> #include<cctype> #include<cstdio> #include<utility> #include<queue> #include<stack> #include<deque> #include<map> #include<set> #include<bitset> #include<vector> #include<algorithm> #include<cstdlib> #define INF 1000000000 #define op(x) t[x].op #define ll long long #define mx(p) t[p].mx #define tag(p) t[p].tag #define midx ((l+r)>>1) #define midy ((u+d)>>1) #define zs (p<<2)+1 #define ys (p<<2)+2 #define zx (p<<2)+3 #define yx (p<<2)+4 #define max(x,y) ((x)>(y)?(x):(y)) #define RE register using namespace std; char buf[1<<15],*fs,*ft; inline char getc() { return (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<15,stdin),fs==ft))?0:*fs++; } inline int read() { RE int x=0,f=1;RE char ch=getc(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getc();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getc();} return x*f; } const int MAXN=1010; int n,m,Q; struct wy { int mx,tag; }t[MAXN*MAXN<<4]; inline void pushdown(RE int p,RE int l,RE int r,RE int u,RE int d) { mx(zs)=tag(p); tag(zs)=tag(p); if(l!=r) { mx(ys)=tag(p); tag(ys)=tag(p); if(u!=d) { mx(yx)=tag(p); tag(yx)=tag(p); } } if(u!=d) { mx(zx)=tag(p); tag(zx)=tag(p); } tag(p)=0;return; } inline void change(RE int p,RE int l,RE int r,RE int u,RE int d,RE int L,RE int R,RE int U,RE int D,RE int x) { if(L<=l&&R>=r&&U<=u&&D>=d) { mx(p)=x; tag(p)=x; return; } if(tag(p))pushdown(p,l,r,u,d); if(L<=midx) { if(U<=midy) { change(zs,l,midx,u,midy,L,R,U,D,x); mx(p)=max(mx(p),mx(zs)); } if(D>midy&&u!=d) { change(zx,l,midx,midy+1,d,L,R,U,D,x); mx(p)=max(mx(p),mx(zx)); } } if(R>midx&&l!=r) { if(U<=midy) { change(ys,midx+1,r,u,midy,L,R,U,D,x); mx(p)=max(mx(p),mx(ys)); } if(D>midy&&u!=d) { change(yx,midx+1,r,midy+1,d,L,R,U,D,x); mx(p)=max(mx(p),mx(yx)); } } return; } inline int ask(RE int p,RE int l,RE int r,RE int u,RE int d,RE int L,RE int R,RE int U,RE int D) { if(L<=l&&R>=r&&U<=u&&D>=d)return mx(p); if(tag(p))pushdown(p,l,r,u,d); RE int ans=0,w; if(L<=midx) { if(U<=midy) { w=ask(zs,l,midx,u,midy,L,R,U,D); ans=max(ans,w); } if(D>midy&&u!=d) { w=ask(zx,l,midx,midy+1,d,L,R,U,D); ans=max(ans,w); } } if(R>midx&&l!=r) { if(U<=midy) { w=ask(ys,midx+1,r,u,midy,L,R,U,D); ans=max(ans,w); } if(D>midy&&u!=d) { w=ask(yx,midx+1,r,midy+1,d,L,R,U,D); ans=max(ans,w); } } return ans; } int main() { freopen("1.in","r",stdin); n=read();m=read();Q=read(); while(Q--) { RE int d,s,h,x,y; d=read();s=read();h=read(); x=read();y=read();//x,y x+d-1 y x y+s-1 x+d-1 y+s-1 RE int ans=ask(0,1,n,1,m,x+1,x+d,y+1,y+s); //cout<<x+1<<' '<<y+1<<' '<<x+d<<' '<<y+s<<' '<<h<<endl; //cout<<ans<<endl; change(0,1,n,1,m,x+1,x+d,y+1,y+s,ans+h); } printf("%d ",mx(0)); return 0; }