2017-05-26

【tyvj1518】CPU监控

本文为博主原创，未经许可不得转载

有关线段树历史最大值的题目

具体做法参照吉司机的论文

居然1A了，好开心啊

#include<bits/stdc++.h>
#define FILE "read"
#define MAXN 100100
#define cmax(a,b) a=max(a,b)
#define cmin(a,b) a=min(a,b)
using namespace std;
struct node{int v[2],delta[2],cover[2];}tr[MAXN<<2];
int n,m;
inline int read(){
	int x=0,f=1;  char ch=getchar();
	while(!isdigit(ch))  {if(ch=='-')  f=-1;  ch=getchar();}
	while(isdigit(ch))  {x=x*10+ch-'0';  ch=getchar();}
	return x*f;
}
void relord(int p){
	tr[p].v[0]=max(tr[p<<1].v[0],tr[p<<1|1].v[0]);
	cmax(tr[p].v[1],tr[p<<1].v[1]);
	cmax(tr[p].v[1],tr[p<<1|1].v[1]);
}
void add(int p,int value){
	cmax(tr[p].v[1],tr[p].v[0]+=value);
	if(tr[p].cover[0]!=(1<<31)) cmax(tr[p].cover[1],tr[p].cover[0]+=value);
	else cmax(tr[p].delta[1],tr[p].delta[0]+=value);
}
void cov(int p,int value){
	cmax(tr[p].cover[1],tr[p].cover[0]=value);
	cmax(tr[p].v[1],tr[p].v[0]=value);
	tr[p].delta[0]=0;
}
void his_add(int p,int value){
	cmax(tr[p].v[1],tr[p].v[0]+value);
	if(tr[p].cover[0]!=(1<<31)) cmax(tr[p].cover[1],tr[p].cover[0]+value);
	else cmax(tr[p].delta[1],tr[p].delta[0]+value);
}
void his_cov(int p,int value){
	cmax(tr[p].cover[1],value);
	cmax(tr[p].v[1],value);
}
void pushdown(int p){
	if(tr[p].delta[1]){
		his_add(p<<1,tr[p].delta[1]);
		his_add(p<<1|1,tr[p].delta[1]);
		tr[p].delta[1]=0;
	}
	if(tr[p].cover[1]!=(1<<31)){
		his_cov(p<<1,tr[p].cover[1]);
		his_cov(p<<1|1,tr[p].cover[1]);
		tr[p].cover[1]=(1<<31);
	}
	if(tr[p].delta[0]){
		add(p<<1,tr[p].delta[0]);
		add(p<<1|1,tr[p].delta[0]);
		tr[p].delta[0]=0;
	}
	if(tr[p].cover[0]!=(1<<31)){
		cov(p<<1,tr[p].cover[0]);
		cov(p<<1|1,tr[p].cover[0]);
		tr[p].cover[0]=(1<<31);
	}
}
void build(int p,int l,int r){
	tr[p].cover[0]=tr[p].cover[1]=tr[p].v[1]=(1<<31);
	if(l==r) {tr[p].v[0]=tr[p].v[1]=read(); return;}
	int mid=(l+r)>>1;
	build(p<<1,l,mid); build(p<<1|1,mid+1,r);
	relord(p);
}
int ask_max(int p,int l,int r,int x,int y){
	if(x>r||y<l) return (1<<31);
	if(x<=l&&y>=r) return tr[p].v[0];
	pushdown(p);  
	int mid=(l+r)>>1;
	return max(ask_max(p<<1,l,mid,x,y),ask_max(p<<1|1,mid+1,r,x,y));
}
int ask_his_max(int p,int l,int r,int x,int y){
	if(x>r||y<l) return (1<<31);
	if(x<=l&&y>=r) return tr[p].v[1];
	pushdown(p);
	int mid=(l+r)>>1;
	return max(ask_his_max(p<<1,l,mid,x,y),ask_his_max(p<<1|1,mid+1,r,x,y));
}
void updata1(int p,int l,int r,int x,int y,int value){
	if(x>r||y<l) return;
	if(x<=l&&y>=r) {add(p,value); return;}
	pushdown(p);
	int mid=(l+r)>>1;
	updata1(p<<1,l,mid,x,y,value); updata1(p<<1|1,mid+1,r,x,y,value);
	relord(p);
}
void updata2(int p,int l,int r,int x,int y,int value){
	if(x>r||y<l) return;
	if(x<=l&&y>=r) {cov(p,value); return;}
	pushdown(p);
	int mid=(l+r)>>1;
	updata2(p<<1,l,mid,x,y,value); updata2(p<<1|1,mid+1,r,x,y,value);
	relord(p);
}
int main(){
	freopen(FILE".in","r",stdin);
	freopen(FILE".out","w",stdout);
	n=read();  build(1,1,n);
	m=read();
	for(int i=1;i<=m;++i){
		char ch[5]; scanf("%s",ch); int l=read(),r=read();
		if(ch[0]=='Q') printf("%d\n",ask_max(1,1,n,l,r));
		else if(ch[0]=='A') printf("%d\n",ask_his_max(1,1,n,l,r));
		else if(ch[0]=='P') {int x=read(); updata1(1,1,n,l,r,x);}
		else {int x=read(); updata2(1,1,n,l,r,x);}
	}
	return 0;
}

本文标题:【tyvj1518】CPU监控

文章作者:chty

发布时间:2017年05月26日 - 20时50分

最后更新:2018年03月02日 - 17时31分

许可协议:本文为博主原创，未经许可不得转载。