UOJ164 V
题意:维护一个数列$a_1...a_n$,有以下5种操作:
- $a_l..a_r=a_l..a_r +x$
- $a_l..a_r=max(a_l..a_r-x,0)$
- $a_l..a_r=x$
- 查询$a_x$
查询$a_x$的历史最大值
题解:
初看时很容易想到线段树。但是有三个操作$+x$,$-x$并对0取$max$,和赋值,好像不是很好维护标记。
我们可以用一个二元组$(a,b)$表示一个标记,意思是将x变为$\max(x+a,b)$。
那么前三个操作就变成了分别给$l..r$打上$(x,0)$,$(-x,0)$,$(-\infty,x)$的标记,开始的赋初值也可以转化为一个标记。
下传标记时要注意先后次序。
标记下传形如:
$$(a,b)+(c,d)=(a+c,\max(b+c,d))$$
注意$(a,b)$是原来的标记。
事实上真正代码中应该是$(a,b)+(c,d)=(\max(a+c,-\infty),\max(b+c,d))$
因为有可能两个甚至三个tag都是形如$(-\infty,x)$,或者是在$(-\infty,x)$的基础上再上一些$(-x,0)$的tag,所以为了避免得到的$a+c < -\infty$甚至爆long long 变为大正数,再代码中应该这么写。
最后查询的时候一路下传标记。最后叶子节点上的tag设为$(a,b)$,则答案为$\max(a,b)$
这样就可以维护1,2,3,4操作了。
对于操作5,要求维护历史最大值。
那么我们就在放标记、下传标记的时候维护一下$a$的最大值和$b$的最大值(同样记作$(a,b)$)。
对于下传时维护最大值,因为可能一个节点上存了多个标记合并以后的标记,所以不能单纯下传后维护最大值。设双亲节点中存的最大值为$(a,b)$,孩子节点中当前的标记为$(c,d)$,则孩子节点中的最大值变为$(c+a,\max(d+a,b))$
每次下传以后需要把标记和维护的最大值清空。
代码:
/*
Author: CNYALI_LK
LANG: C++
PROG: uoj164.cpp
*/
#include<bits/stdc++.h>
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define all(x) x.begin(),x.end()
#define end(...) {printf(__VA_ARGS__);exit(0);}
using namespace std;
const double eps=1e-8;
const double PI=acos(-1.0);
typedef long long ll;
template<class T>void chkmin(T &a,T b){a=a<b?a:b;}
template<class T>void chkmax(T &a,T b){a=a>b?a:b;}
template<class T>T sqr(T a){return a*a;}
template<class T>T mmin(T a,T b){return a<b?a:b;}
template<class T>T mmax(T a,T b){return a>b?a:b;}
template<class T>T aabs(T a){return a<0?-a:a;}
#define min mmin
#define max mmax
#define abs aabs
typedef pair<ll,ll> pii;
#define x first
#define y second
#define mp make_pair
const ll ind=-0x3f3f3f3f3f3f3f3f;
namespace seg{
pii tag[2333333],lmt[2333333];
void cmx(pii &a,pii b){
chkmax(a.x,b.x);
chkmax(a.y,b.y);
}
void at(pii &a,pii b){
a.x=max(a.x+b.x,ind);
a.y=max(a.y+b.x,b.y);
}
void push_down(ll x){
pii s=tag[x<<1];
at(s,lmt[x]);
cmx(lmt[x<<1],s);
s=tag[x<<1|1];
at(s,lmt[x]);
cmx(lmt[x<<1|1],s);
at(tag[x<<1],tag[x]);
at(tag[x<<1|1],tag[x]);
tag[x]=lmt[x]=mp(0,0);
}
#define mid ((l+r)>>1)
void atg(ll x,ll l,ll r,ll lx,ll rx,pii tg){
if(l!=r)push_down(x);
if(lx<=l&&r<=rx){
at(tag[x],tg);
cmx(lmt[x],tag[x]);
return;
}
if(lx<=mid)atg(x<<1,l,mid,lx,rx,tg);
if(mid<rx)atg(x<<1|1,mid+1,r,lx,rx,tg);
}
ll query(ll x,ll l,ll r,ll t){
while(l<r){
push_down(x);
if(t<=mid){r=mid;x<<=1;}
else {l=mid+1;x=x<<1|1;}
}
return max(tag[x].x,tag[x].y);
}
ll lquery(ll x,ll l,ll r,ll t){
while(l<r){
push_down(x);
if(t<=mid){r=mid;x<<=1;}
else {l=mid+1;x=x<<1|1;}
}
return max(lmt[x].x,lmt[x].y);
}
}
int main(){
#ifdef cnyali_lk
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
#endif
ll n,m,t,l,r,x;
scanf("%lld%lld",&n,&m);
for(ll i=1;i<=n;++i){
scanf("%lld",&x);
seg::atg(1,1,n,i,i,mp(x,0));
}
while(m){
--m;
scanf("%lld",&t);
if(t==1){
scanf("%lld%lld%lld",&l,&r,&x);
seg::atg(1,1,n,l,r,mp(x,0));
}
else if(t==2){
scanf("%lld%lld%lld",&l,&r,&x);
seg::atg(1,1,n,l,r,mp(-x,0));
}
else if(t==3){
scanf("%lld%lld%lld",&l,&r,&x);
seg::atg(1,1,n,l,r,mp(ind,x));
}
else if(t==4){
scanf("%lld",&x);
printf("%lld\n",seg::query(1,1,n,x));
}
else{
scanf("%lld",&x);
printf("%lld\n",seg::lquery(1,1,n,x));
}
}
return 0;
}