关键词：
二维线段树板子，注意标记永久化。
1 #include<bits/stdc++.h> 2 using namespace std; 3 int ans,A,B,n,ql,qr,qd,qu; 4 struct Querx 5 6 int v[3005],tag[3005]; 7 void change(int k,int l,int r,int L,int R,int w) 8 9 v[k]=max(v[k],w); 10 if(l==L&&r==R)tag[k]=max(tag[k],w);return; 11 int m=l+r>>1; 12 if(R<=m)change(k<<1,l,m,L,R,w); 13 else if(L>m)change(k<<1|1,m+1,r,L,R,w); 14 else change(k<<1,l,m,L,m,w),change(k<<1|1,m+1,r,m+1,R,w); 15 16 int query(int k,int l,int r,int L,int R) 17 18 if(l==L&&r==R)return v[k]; 19 int m=l+r>>1;int tmp=tag[k]; 20 if(R<=m)return max(tmp,query(k<<1,l,m,L,R)); 21 else if(L>m)return max(tmp,query(k<<1|1,m+1,r,L,R)); 22 else return max(tmp,max(query(k<<1,l,m,L,m),query(k<<1|1,m+1,r,m+1,R))); 23 24 ; 25 struct Query 26 27 Querx v[3005],tag[3005]; 28 void change(int k,int l,int r,int L,int R,int w) 29 30 v[k].change(1,1,B,qd,qu,w); 31 if(l==L&&r==R)tag[k].change(1,1,B,qd,qu,w);return; 32 int m=l+r>>1; 33 if(R<=m)change(k<<1,l,m,L,R,w); 34 else if(L>m)change(k<<1|1,m+1,r,L,R,w); 35 else change(k<<1,l,m,L,m,w),change(k<<1|1,m+1,r,m+1,R,w); 36 37 int query(int k,int l,int r,int L,int R) 38 39 if(l==L&&r==R)return v[k].query(1,1,B,qd,qu); 40 int m=l+r>>1;int tmp=tag[k].query(1,1,B,qd,qu); 41 if(R<=m)return max(tmp,query(k<<1,l,m,L,R)); 42 else if(L>m)return max(tmp,query(k<<1|1,m+1,r,L,R)); 43 else return max(tmp,max(query(k<<1,l,m,L,m),query(k<<1|1,m+1,r,m+1,R))); 44 45 P; 46 int main() 47 48 scanf("%d%d%d",&A,&B,&n); 49 for(int i=1;i<=n;++i) 50 51 int x,y,z,h,a,b; 52 scanf("%d%d%d%d%d",&x,&y,&z,&a,&b); 53 ql=a+1;qr=a+x;qd=b+1;qu=b+y; 54 ans=P.query(1,1,A,ql,qr); 55 P.change(1,1,A,ql,qr,ans+z); 56 57 qd=1;qu=B;ans=P.query(1,1,B,1,B); 58 printf("%d\n",ans); 59 return 0; 60
bzoj1513[poi2006]tet-tetris3d二维线段树
【BZOJ1513】[POI2006]Tet-Tetris3DDescriptionTask:Tetris3D"Tetris"游戏的作者决定做一个新的游戏,一个三维的版本,在里面很多立方体落在平面板,一个立方体开始落下直到碰上一个以前落下的立方体或者落地即停止.作者想改变一下游戏的目的... 查看详情
bzoj1513[poi2006]tet-tetris3d二维线段树
题目链接BZOJ1513题解真正地理解了一波线段树标记永久化的姿势每个节点维护两个值\(v\)和\(tag\)\(v\)代表儿子中的最值\(tag\)代表未下传的最值显然节点的区间大于等于\(v\)的实际区间而\(tag\)的区间包含节点的区间我们在修改的时... 查看详情
bzoj1513[poi2006]tet-tetris3d(代码片段)
二维线段树板子，注意标记永久化。1#include<bits/stdc++.h>2usingnamespacestd;3intans,A,B,n,ql,qr,qd,qu;4structQuerx56intv[3005],tag[3005];7voidchange(intk,intl,intr,intL,intR,intw)89v[k]=max(v[k],w);10if(l==L&a 查看详情
bzoj1513[poi2006]tet-tetris3d（二维线段树）
【题目链接】 http://www.lydsy.com/JudgeOnline/problem.php?id=1513 【题目大意】 一个立方体开始落下直到碰上一个以前落下的立方体或者落地即停止. 你将知道落下的立方体信息以及位置, 你的任务就是回答所有立方... 查看详情
bzoj1513:[poi2006]tet-tetris3d
DescriptionTask:Tetris3D"Tetris"游戏的作者决定做一个新的游戏,一个三维的版本,在里面很多立方体落在平面板,一个立方体开始落下直到碰上一个以前落下的立方体或者落地即停止.作者想改变一下游戏的目的使得它更大众化,在新游戏... 查看详情
bzoj1520poi2006szk-schools
1520:[POI2006]Szk-SchoolsTimeLimit: 5Sec MemoryLimit: 64MBSubmit: 771 Solved: 398[Submit][Status][Discuss]DescriptionInputOutput如果有可行解,输出最小代价,否则输出NIE.SampleIn 查看详情
bzoj1520[poi2006]szk-schoolskm算法
【BZOJ1520】[POI2006]Szk-SchoolsDescriptionInputOutput如果有可行解,输出最小代价,否则输出NIE.SampleInput5112311513255415103331SampleOutput9题解：二分图最小权匹配裸题，可以直接无脑费用流，不过这里就当复习一下KM算法了。#include<cstdio>#inclu... 查看详情
bzoj1510[poi2006]kra-thedisks*
bzoj1510[POI2006]Kra-TheDisks题意：一个瓶子有n个节，每个节有一个宽度。现在要从上往下扔m个盘子，如果盘子的下一个位置宽度比该盘子的宽度小则盘子会停在这个位置。问最后一个盘子会停在那个位置。n，m≤300000。题解：首先利... 查看详情
[bzoj1510][poi2006]kra-thedisks_暴力
Kra-TheDisksbzoj-1510POI-2006题目大意：题目链接。注释：略。想法：不难发现其实只有前缀最小值是有效的。进而我们把盘子一个一个往里放，弄一个自底向上的指针往上蹦即可。时间复杂度$O(n)$。Code：#include<iostream>#include<cst... 查看详情
bzoj1511:[poi2006]okr-periodsofwordskmp(代码片段)
n-ne[n]是n的最长循环节长度，其实就是n-最短前缀=后缀长度然后我们要求最短循环节，其实就是ne一直往前跳，跳到不能跳为止，这时的n-ne[n]就是n的最短循环节长度#include<iostream>#include<cstdio>usingnamespacestd;constintN=1000005;in... 查看详情
bzoj1520[poi2006]szk-schools费用流
题目描述输入输出如果有可行解,输出最小代价,否则输出NIE.样例输入5112311513255415103331样例输出9题解费用流设xi表示学生，yi表示编号，那么S->xi，容量为1，费用为0；xi->能够使得xi接受的yj，容量为1，费用为按照题目中计算... 查看详情
bzoj1511[poi2006]okr-periodsofwordskmp-next数组
原文地址：http://www.cnblogs.com/GXZlegend/p/6827027.html题目描述一个串是有限个小写字符的序列,特别的,一个空序列也可以是一个串.一个串P是串A的前缀,当且仅当存在串B,使得A=PB.如果PA并且P不是一个空串,那么我们说P是A的一个proper前缀... 查看详情
bzoj1515[poi2006]lis-thepostman有向图欧拉回路(代码片段)
LINK：Lis-ThePostman看完题觉得虽然容易发现是有向图欧拉回路但是觉得很难解决这个问题。先分析一下有向图的欧拉回路：充要条件图中每个点的入度-出度=0且整张图是一个强连通分量。证明：首先考虑前者这个思想是从一个点出... 查看详情
bzoj1513
二维线段树听说二维线段树不能下传标记？就是裸的二维线段树，由于每次高度只能增加，所以我们就可以标记永久化每个线段树里有两个数组,mx和mark，每次修改路径上所有mx都要修改，mark是区间的精确覆盖修改每次查询把路... 查看详情
[poi2006]ork-ploughing
[POI2006]ORK-Ploughinghttps://www.luogu.org/problemnew/show/P3444题目描述(Byteasar)想耕种他那块矩形的田,他每次能耕种矩形的一边(上下左右都行),在他每次耕完后,剩下的田也一定是矩形,每块小区域边长为(1),耕地的长宽分别为(m)和(n),不幸的是(... 查看详情
bzoj2428:[haoi2006]均分数据
二次联通门: BZOJ2428:[HAOI2006]均分数据 /*BZOJ2428:[HAOI2006]均分数据模拟退火初体验完全随机化算法估计对我这种非酋来说的话估计是用处不大了吧23333*/#include<cstdio>#include<iostream>#include<cstdlib>#incl 查看详情
[bzoj2527][poi2011]meteors
2527:[Poi2011]MeteorsTimeLimit:60Sec MemoryLimit:128MBSubmit:1807 Solved:646[Submit][Status][Discuss]DescriptionByteotianInterstellarUnion(BIU)hasrecentlydiscoveredanewplanetinan 查看详情
bzoj2213[poi2011]differencedp
【BZOJ2213】[Poi2011]DifferenceDescriptionAwordconsistingoflower-caselettersoftheEnglishalphabet(‘a‘-‘z‘)isgiven.Wewouldliketochooseanon-emptycontiguous(i.e.one-piece)fragmentofthewordsoastomaximisethed 查看详情