UOJ164 V
题意：维护一个数列\(a_1...a_n\)，有以下5种操作： 1. \(a_l..a_r=a_l..a_r +x\) 2. \(a_l..a_r=max(a_l..a_r-x,0)\) 3. \(a_l..a_r=x\) 4. 查询\(a_x\) 5. 查询\(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;
}