Tyvj 1518 CPU监控（线段树）
题目描述：
Bob需要一个程序来监视CPU使用率。这是一个很繁琐的过程，为了让问题更加简单，Bob会慢慢列出今天会在用计算机时做什么事。 Bob会干很多事，除了跑暴力程序看视频之外，还会做出去玩玩和用鼠标乱点之类的事，甚至会一脚踢掉电源……这些事有的会让做这件事的这段时间内CPU使用率增加或减少一个值；有的事还会直接让CPU使用率变为一个值。 当然Bob会询问：在之前给出的事件影响下，CPU在某段时间内，使用率最高是多少。有时候Bob还会好奇地询问，在某段时间内CPU曾经的最高使用率是多少。 为了使计算精确，使用率不用百分比而用一个整数表示。 不保证Bob的事件列表出了莫名的问题，使得使用率为负………………
输入格式：
第一行一个正整数T，表示Bob需要监视CPU的总时间。 然后第二行给出T个数表示在你的监视程序执行之前，Bob干的事让CPU在这段时间内每个时刻的使用率达已经达到了多少。 第三行给出一个数E，表示Bob需要做的事和询问的总数。 接下来E行每行表示给出一个询问或者列出一条事件： Q X Y:询问从X到Y这段时间内CPU最高使用率 A X Y:询问从X到Y这段时间内之前列出的事件使CPU达到过的最高使用率 P X Y Z:列出一个事件这个事件使得从X到Y这段时间内CPU使用率增加Z C X Y Z:列出一个事件这个事件使得从X到Y这段时间内CPU使用率变为Z 时间的单位为秒，使用率没有单位。 X和Y均为正整数（X<=Y），Z为一个整数。 从X到Y这段时间包含第X秒和第Y秒。 保证必要运算在有符号32位整数以内。
输出格式：
对于每个询问，输出一行一个整数回答。
没看懂题？没关系，将题目抽象化一下：
题目大意：
给出序列,要求查询一些区间的最大值、历史最大值，支持区间加、区间修改。序列长度（n）和操作数（m）<=1e5。
题解：
乍一看，这不线段树水题吗！其实不然，此题在洛谷上是黑题，模板很简单，难度在于标记下传。
我们将操作分开来看。首先，这颗线段树要支持区间查询最大值，这个很简单，然后要支持区间赋值和加值。
赋值和加值得结合让此题有了一些难度。对于任何一个点，不能同时拥有两个标记，否则会冲突，因为两个标记是相互影响的，所以操作的先后也就意味着答案。幸运的是，如果我们在每一步操作之前都先下传标记，那么就会解决冲突。
标记的下传是难点。我们先不考虑历史最大值，那么我们用到的标记只有两个，一个为ad，记录加值，另一个为se，记录赋值，两个标记不能同时出现，所以一次操作最多下传一个标记，只下传有信息的标记即可，下传时，由于子节点可能有自己的信息，所以要进行分类讨论：
1、若父节点有ad值，子节点有ad值，累加即可;
2、若父节点有ad值，子节点有se值，则在子节点的se值上加上ad；
3、若父节点有se值，子节点有ad值，则清空字节点的ad值，将子节点的色se值赋成父节点的se值;
4、若父节点有se值，子节点有se值，则用父节点的se值覆盖子节点的se值;
5、若子节点无信息，直接下传。
分的类别很多，但是我们可以将某些性质相似的情况合并，减少代码量，例如第5条就很好合并。对于原因作者不再过多陈述，应该很简单，想想就能明白。
至此我们解决了冲突问题。
然后，我们再考虑历史最大值的问题。
由于标记之打在最上面一层，所以标记的信息可能在传到子节点之前，就已经被覆盖掉。我们为了维护历史最大值，还要相对维护ad值和se值的历史最大值。用had和hse分别代表ad和se的历史最大值。
那么我们可以发现，当标记下传时，信息就可以更新到子节点，所以我们以标记下传为间隔维护had和hse。
历史最大值hma有如下几条来源：
1、ma被直接更新时的值;
2、标记下传时的hse值;
3、标记下传时had和当前ma值之和。
所以每次下传标记时，用以上三条更新即可，但要注意顺序，应先进行2、3再进行1,因为进行1时ma的值改变，其属性不再属于标记下传以前，所以会得到错误答案。
接下来便是had与hse的维护问题。
维护较为简单，我们只要已标记下传为间隔，每次用当前的ad之和se值与父节点的had和hse值更新。每次标记下传时，将had，ad，hse和se都清空，代表一个过程的结束。
had和hse可以由父节点的had和hse值转移，与上面5条类似，注意had和hse还可以直接由ad值和se值更新。
其实我们发现此操作可以分成四部分：
1、用父节点的ad更新;
2、用父节点的had更新;
3、用父节点的se更新;
4、用父节点的hse更新;
这四种操作可写为四个函数，进一步降低代码复杂度。在add和set的函数里，只需进行操作1和3，因为没有父节点的影响，在标记下传时，先进行2、4，再进行1、3，保证状态不会混乱。
要注意的是更新的状态层次，要保持一致，在此题中就是以标记下传分割层次，不要串层更新。
通俗的说，就是我用标记更新儿子，儿子就不会用标记更新自己。add和set函数内的更新其实就是标记下传的一部分，标记下传应与函数内的语句一致。
要注意将se和hse的初值赋为负极大值，排除0的干扰。
此题除了标记下传，其他语句都是正常的线段树打法，不要将问题复杂化。
还有，注意细节，这题打多了可过，打少了一定WA。
复杂度O（nlogn）
Code：
#include<iostream>
#include<cstdio>
using namespace std;
const int N=1e5+;
const int inf=;
int n,m;
struct seg{
int l,r;
int ma,hma;
int ad,had;
int se,hse;
}t[N<<];
char get()
{
char c=getchar();
while(c!='A'&&c!='C'&&c!='P'&&c!='Q')
c=getchar();
return c;
}
void pushup(int k)
{
t[k].ma=max(t[k<<].ma,t[k<<|].ma);
t[k].hma=max(t[k<<].hma,t[k<<|].hma);
}
void pushdown(int k)
{
if(t[k].l!=t[k].r)
{
for(int i=;i<=;i++)
{
int ch=k<<|i;
t[ch].hma=max(t[ch].hma,t[ch].ma+t[k].had);
if(t[ch].hse!=-inf)
t[ch].hse=max(t[ch].hse,t[ch].se+t[k].had);
else
t[ch].had=max(t[ch].had,t[k].had+t[ch].ad);
t[ch].hma=max(t[ch].hma,t[k].hse);
t[ch].hse=max(t[ch].hse,t[k].hse);
if(t[k].ad!=)
{
t[ch].ma+=t[k].ad;
t[ch].hma=max(t[ch].hma,t[ch].ma);
if(t[ch].se==-inf)
{
t[ch].ad+=t[k].ad;
t[ch].had=max(t[ch].had,t[ch].ad);
}
else
{
t[ch].se+=t[k].ad;
t[ch].hse=max(t[ch].hse,t[ch].se);
}
}
else if(t[k].se!=-inf)
{
t[ch].ma=t[k].se;
t[ch].hma=max(t[ch].hma,t[ch].ma);
t[ch].se=t[k].se;
t[ch].hse=max(t[k].se,t[ch].hse);
t[ch].ad=;
}
}
}
t[k].se=t[k].hse=-inf;
t[k].ad=t[k].had=;
}
void build(int k,int l,int r)
{
t[k].l=l;
t[k].r=r;
if(l==r)
{
scanf("%d",&t[k].ma);
t[k].hma=t[k].ma;
t[k].ad=t[k].had=;
t[k].se=t[k].hse=-inf;
return;
}
int mid=(l+r)>>;
build(k<<,l,mid);
build(k<<|,mid+,r);
t[k].se=t[k].hse=-inf;
pushup(k);
}
void add(int k,int l,int r,int x)
{
pushdown(k);
if(t[k].l>=l&&t[k].r<=r)
{
t[k].ma+=x;
t[k].hma=max(t[k].hma,t[k].ma);
if(t[k].se==-inf)
{
t[k].ad+=x;
t[k].had=max(t[k].had,t[k].ad);
}
else
{
t[k].se+=x;
t[k].hse=max(t[k].hse,t[k].se);
}
return;
}
int mid=(t[k].l+t[k].r)>>;
if(l<=mid)
add(k<<,l,r,x);
if(r>mid)
add(k<<|,l,r,x);
pushup(k);
}
void change(int k,int l,int r,int x)
{
pushdown(k);
if(t[k].l>=l&&t[k].r<=r)
{
t[k].ma=x;
t[k].hma=max(t[k].hma,t[k].ma);
t[k].se=x;
t[k].hse=max(x,t[k].hse);
t[k].ad=;
return;
}
int mid=(t[k].l+t[k].r)>>;
if(l<=mid)
change(k<<,l,r,x);
if(r>mid)
change(k<<|,l,r,x);
pushup(k);
}
int que(int k,int l,int r)
{
pushdown(k);
if(t[k].l>=l&&t[k].r<=r)
return t[k].ma;
int mid=(t[k].l+t[k].r)>>;
if(r<=mid)
return que(k<<,l,r);
else if(l>mid)
return que(k<<|,l,r);
else
return max(que(k<<,l,mid),que(k<<|,mid+,r));
}
int queh(int k,int l,int r)
{
pushdown(k);
if(t[k].l>=l&&t[k].r<=r)
return t[k].hma;
int mid=(t[k].l+t[k].r)>>;
if(r<=mid)
return queh(k<<,l,r);
else if(l>mid)
return queh(k<<|,l,r);
else
return max(queh(k<<,l,mid),queh(k<<|,mid+,r));
}
int main()
{
scanf("%d",&n);
build(,,n);
scanf("%d",&m);
for(int i=;i<=m;i++)
{
int x,y,z;
char op=get();
if(op=='A')
{
scanf("%d%d",&x,&y);
printf("%d\n",queh(,x,y));
}
else if(op=='C')
{
scanf("%d%d%d",&x,&y,&z);
change(,x,y,z);
}
else if(op=='P')
{
scanf("%d%d%d",&x,&y,&z);
add(,x,y,z);
}
else
{
scanf("%d%d",&x,&y);
printf("%d\n",que(,x,y));
}
}
return ;
}
祝你们AC！
最新文章
- 学习SpringMVC——你们要的REST风格的CRUD来了
- Arduino uno LED灯实验
- .NET Web开发笔记
- ubuntu下安装lrzsz
- memcache原理、简单使用、分布式实现方案
- Intellij Idea 2016 配置Tomcat虚拟目录
- 关于页面 reflow 和 repaint
- WindowsPhone8解锁提示IpOverUsbSvc问题
- Oracle笔记 一、oracle的安装、sqlplus的使用
- hdu 2254 奥运
- Python基础 - 迭代
- 对sql进行分页处理（Oracle版）
- ASP.NET使用WebApi接口实现与Android客户端的交互（图片或字符串的接收与回传）
- 爬起点小说day03
- PAGELATCH_x 等待--转载
- 一个整数数组，有n个整数，如何找其中m个数的和等于另外n-m个数的和？
- Awvs、Snort的下载安装
- 转-软件测试人员在工作中如何运用Linux
- IE8浏览器官方下载 包含Windows中繁英文各个版本
- FUSE 文件系统 example部分 源码注释 (libfuse 2.9.9)