题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=1513
题意：矩形求 max，矩形赋值。
二维线段树即可，本质上就是树套树，内外层线段树分别维护行列。
需要注意的是外层线段树没法 pushup 和 pushdown，复杂度无法接受。所以标记永久化即可。好多题解内层也标记永久化了，其实没有必要。
标记永久化即在修改时路径更新上传标记，找到区间后更新下传标记。
查询时路径上带上下传标记查询，找到区间后用上传标记更新即可。
此题卡空间，需要动态开点，可能是我写的挫，内外层都动态开点了... 跑的很慢...
有些题解直接不动态开点开的三倍空间，实际上是萎的好像？ 我记得线段树编号最大会到 4n-3 好像？
啊我随便口胡的 T.T
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 |
#include <cmath> #include <queue> #include <cstdio> #include <iomanip> #include <cstdlib> #include <cstring> #include <iostream> #include <algorithm> #define N 1010 #define ll long long using namespace std; char xB[1<<15],*xS=xB,*xT=xB; #define getchar() (xS==xT&&(xT=(xS=xB)+fread(xB,1,1<<15,stdin),xS==xT)?0:*xS++) inline int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } inline int Mx(int a,int b) {return a>b?a:b;} int n,m,q; struct ins_seg { int tag[N<<1],mx[N<<1]; int ch[N<<1][2],tot; void cov(int x,int v) { tag[x]=Mx(tag[x],v); mx[x]=Mx(mx[x],v); } void pushdown(int x) { if(tag[x]) { if(!ch[x][0])ch[x][0]=++tot; if(!ch[x][1])ch[x][1]=++tot; cov(ch[x][0],tag[x]),cov(ch[x][1],tag[x]); tag[x]=0; } } void pushup(int x) { mx[x]=Mx(mx[ch[x][0]],mx[ch[x][1]]); } void update(int &x,int l,int r,int L,int R,int v) { if(!x)x=++tot; if(l>=L&&r<=R) { cov(x,v); return ; } pushdown(x); int mid=(l+r)>>1; if(L<=mid) update(ch[x][0],l,mid,L,R,v); if(R>mid) update(ch[x][1],mid+1,r,L,R,v); pushup(x); } int ask(int x,int l,int r,int L,int R) { if(!x)return 0; if(l>=L&&r<=R)return mx[x]; pushdown(x); int mid=(l+r)>>1,ret=0; if(L<=mid) ret=Mx(ret,ask(ch[x][0],l,mid,L,R)); if(R>mid) ret=Mx(ret,ask(ch[x][1],mid+1,r,L,R)); return ret; } }; struct out_seg { ins_seg tag[N<<1],mx[N<<1]; int r_tag[N<<1],r_mx[N<<1]; int ch[N<<1][2],tot; void modify(int &x,int l,int r,int L,int R,int c,int d,int e) { if(!x)x=++tot; mx[x].update(r_mx[x],1,m,c,d,e); if(l>=L&&r<=R) { tag[x].update(r_tag[x],1,m,c,d,e); return ; } int mid=(l+r)>>1; if(L<=mid) modify(ch[x][0],l,mid,L,R,c,d,e); if(R>mid) modify(ch[x][1],mid+1,r,L,R,c,d,e); } int ask(int x,int l,int r,int L,int R,int c,int d) { int ret=tag[x].ask(r_tag[x],1,m,c,d); if(l>=L&&r<=R) return Mx(ret,mx[x].ask(r_mx[x],1,m,c,d)); int mid=(l+r)>>1; if(L<=mid) ret=Mx(ret,ask(ch[x][0],l,mid,L,R,c,d)); if(R>mid) ret=Mx(ret,ask(ch[x][1],mid+1,r,L,R,c,d)); return ret; } }T; int rt; int main() { n=read(),m=read(),q=read(); while(q--) { int c=read(),d=read(),e=read(),a=read(),b=read(); T.modify(rt,1,n,a+1,a+c,b+1,b+d,T.ask(1,1,n,a+1,a+c,b+1,b+d)+e); } printf("%d\n",T.ask(1,1,n,1,n,1,m)); } |
Comments | 1 条评论
博主真菜！