2017-05-26

【清华集训2015】V

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

AC通道

思路很妙的一道题

我们定义一种新的标记：(a,b)表示先加上a后对b取max

那么两个标记(a,b)(c,d)的合并就是(a+c,max(b+c,d))

然后就是维护历史最大值那一套理论

用pair维护标记很爽啊

#include<bits/stdc++.h>
#define FILE "read"
#define MAXN 500100
#define cmax(a,b) a=max(a,b)
#define cmin(a,b) a=min(a,b)
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pii;
#define INF (ll)1e18
pii A[MAXN<<2],B[MAXN<<2];
int n,m;
inline int read(){
	int x=0,f=1;  char ch=getchar();
	while(ch>'9'||ch<'0')  {if(ch=='-')  f=-1;  ch=getchar();}
	while(ch>='0'&&ch<='9')  {x=x*10+ch-'0';  ch=getchar();}
	return x*f;
}
void build(int p,int l,int r){
	if(l==r)  {A[p].first=A[p].second=B[p].first=B[p].second=read(); return;}
	int mid=(l+r)>>1;
	build(p<<1,l,mid); 
	build(p<<1|1,mid+1,r);
}
pii merge(pii A,pii B){
	ll a=A.first,b=A.second,c=B.first,d=B.second;
	return make_pair(max(a+c,-INF),max(b+c,d));
}
pii getmax(pii A,pii B){
	ll a=A.first,b=A.second,c=B.first,d=B.second;
	return make_pair(max(a,c),max(b,d));
}
void pushdown(int p){
	B[p<<1]=getmax(B[p<<1],merge(A[p<<1],B[p]));
	B[p<<1|1]=getmax(B[p<<1|1],merge(A[p<<1|1],B[p]));
	A[p<<1]=merge(A[p<<1],A[p]);
	A[p<<1|1]=merge(A[p<<1|1],A[p]);
	A[p]=make_pair(0,0);
	B[p]=make_pair(0,0);
}
void updata(int p,int l,int r,int x,int y,pii v){
	if(x<=l&&y>=r){
		A[p]=merge(A[p],v);
		B[p]=getmax(B[p],A[p]);
		return;
	}
	pushdown(p);
	int mid=(l+r)>>1;
	if(x<=mid) updata(p<<1,l,mid,x,y,v);  
	if(y>mid)  updata(p<<1|1,mid+1,r,x,y,v);
}
ll query(int p,int l,int r,int x,int opt){
	if(l==r){
		if(opt==4) return max(A[p].first,A[p].second);
		else return max(B[p].first,B[p].second);
	}
	pushdown(p);
	int mid=(l+r)>>1;
	if(x<=mid) return query(p<<1,l,mid,x,opt);
	else return query(p<<1|1,mid+1,r,x,opt);
}
int main(){
	freopen(FILE".in","r",stdin);
	freopen(FILE".out","w",stdout);
	n=read();  m=read();  build(1,1,n);
	for(int i=1;i<=m;++i){
		int opt=read();
		if(opt==1){
			int l=read(),r=read(),x=read();
			updata(1,1,n,l,r,make_pair(x,-INF));
		}
		else if(opt==2){
			int l=read(),r=read(),x=read();
			updata(1,1,n,l,r,make_pair(-x,0));
		}
		else if(opt==3){
			int l=read(),r=read(),x=read();
			updata(1,1,n,l,r,make_pair(-INF,x));
		}
		else{
			int x=read();
			printf("%lld\n",query(1,1,n,x,opt));
		}
	}
	return 0;
}

本文标题:【清华集训2015】V

文章作者:chty

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

最后更新:2018年06月08日 - 18时45分

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