木易电影 2018-05-17
BZOJ1513
真正地理解了一波线段树标记永久化的姿势
每个节点维护两个值\(v\)和\(tag\)
\(v\)代表儿子中的最值
\(tag\)代表未下传的最值
显然节点的区间大于等于\(v\)的实际区间
而\(tag\)的区间包含节点的区间
我们在修改的时候,沿路\(v\)都要修改,底层\(tag\)修改
我们在查询的时候,沿路\(tag\)都要查询,底层\(v\)查询
\(upd:\)理解层面上看,和普通线段树是一样的嘛,,,,
#include<algorithm> #include<iostream> #include<cstring> #include<cstdio> #include<cmath> #include<map> #define Redge(u) for (int k = h[u],to; k; k = ed[k].nxt) #define REP(i,n) for (int i = 1; i <= (n); i++) #define mp(a,b) make_pair<int,int>(a,b) #define cls(s) memset(s,0,sizeof(s)) #define cp pair<int,int> #define LL long long int #define ls (u << 1) #define rs (u << 1 | 1) using namespace std; const int maxn = 4005,maxm = 5000005,INF = 1000000000; inline int read(){ int out = 0,flag = 1; char c = getchar(); while (c < 48 || c > 57){if (c == '-') flag = -1; c = getchar();} while (c >= 48 && c <= 57){out = (out << 3) + (out << 1) + c - 48; c = getchar();} return out * flag; } int n,D,S; struct segx{ int mx[maxm],lc[maxm],rc[maxm],tag[maxm],cnt; void modify(int& u,int l,int r,int L,int R,int v){ if (!u) u = ++cnt; mx[u] = max(mx[u],v); if (l >= L && r <= R){tag[u] = max(tag[u],v); return;} int mid = l + r >> 1; if (mid >= L) modify(lc[u],l,mid,L,R,v); if (mid < R) modify(rc[u],mid + 1,r,L,R,v); } int query(int u,int l,int r,int L,int R){ if (!u) return 0; if (l >= L && r <= R) return mx[u]; int mid = l + r >> 1,ans = tag[u]; if (mid >= R) return max(ans,query(lc[u],l,mid,L,R)); if (mid < L) return max(ans,query(rc[u],mid + 1,r,L,R)); return max(ans,max(query(lc[u],l,mid,L,R),query(rc[u],mid + 1,r,L,R))); } }Seg; struct segy{ int rt[maxn],tag[maxn]; void modify(int u,int l,int r,int L,int R,int ll,int rr,int v){ Seg.modify(rt[u],1,S,ll,rr,v); if (l >= L && r <= R){Seg.modify(tag[u],1,S,ll,rr,v); return;} int mid = l + r >> 1; if (mid >= L) modify(ls,l,mid,L,R,ll,rr,v); if (mid < R) modify(rs,mid + 1,r,L,R,ll,rr,v); } int query(int u,int l,int r,int L,int R,int ll,int rr){ if (l >= L && r <= R) return Seg.query(rt[u],1,S,ll,rr); int mid = l + r >> 1,ans = Seg.query(tag[u],1,S,ll,rr); if (mid >= L) ans = max(ans,query(ls,l,mid,L,R,ll,rr)); if (mid < R) ans = max(ans,query(rs,mid + 1,r,L,R,ll,rr)); return ans; } }T; int main(){ D = read(); S = read(); n = read(); int d,s,h,x0,y0,x,y,xx,yy; while (n--){ d = read(); s = read(); h = read(); x0 = read(); y0 = read(); x = x0 + 1; y = y0 + 1; xx = x0 + d; yy = y0 + s; h += T.query(1,1,D,x,xx,y,yy); T.modify(1,1,D,x,xx,y,yy,h); } printf("%d\n",T.query(1,1,D,1,D,1,S)); return 0; }