给你一个长度为 $n$ 的序列，支持五种操作：
$1\ l\ r\ x$ ：将 $[l,r]$ 内的数加上 $x$ ；
$2\ l\ r\ x$ ：将 $[l,r]$ 内的数减去 $x$ ，并与 $0$ 取 $\text{max}$ ；
$3\ l\ r\ x$ ：将 $[l,r]$ 内的数变为 $x$ ；
$4\ y$ ：询问第 $y$ 个数的值；
$5\ y$ ：询问第 $y$ 个数的历史最大值。
$n,m\le 5\times 10^5,0\le x\le 10^9$
题解
线段树维护历史最值
线段树维护历史最值的方法可以参考 CPU监控 （那道题我是用这道题的方法做的。。。）
那么按照同样的方法，操作1可以看作打标记 $(x,0)$ ，操作2可以看作打标记 $(-x,0)$ ，操作3可以看作打标记 $(-\infty ,x)$ 。
用同样的方法进行标记的维护即可。
由于本题是单点查询，因此可以只考虑标记对原值的影响，不需要维护区间最值及区间历史最值。
时间复杂度 $O(m\log n)$
#include <cstdio>
#include <algorithm>
#define N 500010
#define lson l , mid , x << 1
#define rson mid + 1 , r , x << 1 | 1
using namespace std;
typedef long long ll;
const ll inf = 1ll << 60;
struct data
{
ll x , y;
data(ll a = 0 , ll b = -inf) {x = a , y = b;}
data operator+(const data &a)const {return data(max(x + a.x , -inf) , max(y + a.x , a.y));}
data operator*(const data &a)const {return data(max(x , a.x) , max(y , a.y));}
}ntag[N << 2] , ptag[N << 2];
ll a[N];
inline void pushdown(int x)
{
int l = x << 1 , r = x << 1 | 1;
ptag[l] = ptag[l] * (ntag[l] + ptag[x]);
ntag[l] = ntag[l] + ntag[x];
ptag[r] = ptag[r] * (ntag[r] + ptag[x]);
ntag[r] = ntag[r] + ntag[x];
ptag[x] = ntag[x] = data();
}
void build(int l , int r , int x)
{
ntag[x] = ptag[x] = data();
if(l == r)
{
scanf("%lld" , &a[l]);
return;
}
int mid = (l + r) >> 1;
build(lson) , build(rson);
}
void update(int b , int e , data v , int l , int r , int x)
{
if(b <= l && r <= e)
{
ptag[x] = ptag[x] * (ntag[x] + v);
ntag[x] = ntag[x] + v;
return;
}
pushdown(x);
int mid = (l + r) >> 1;
if(b <= mid) update(b , e , v , lson);
if(e > mid) update(b , e , v , rson);
}
ll query(int p , bool flag , int l , int r , int x)
{
if(l == r)
{
if(flag) return max(a[p] + ptag[x].x , ptag[x].y);
else return max(a[p] + ntag[x].x , ntag[x].y);
}
pushdown(x);
int mid = (l + r) >> 1;
if(p <= mid) return query(p , flag , lson);
else return query(p , flag , rson);
}
int main()
{
int n , m , opt , x , y;
ll z;
scanf("%d%d" , &n , &m);
build(1 , n , 1);
while(m -- )
{
scanf("%d%d" , &opt , &x);
if(opt == 1) scanf("%d%lld" , &y , &z) , update(x , y , data(z , 0) , 1 , n , 1);
if(opt == 2) scanf("%d%lld" , &y , &z) , update(x , y , data(-z , 0) , 1 , n , 1);
if(opt == 3) scanf("%d%lld" , &y , &z) , update(x , y , data(-inf , z) , 1 , n , 1);
if(opt == 4) printf("%lld\n" , query(x , 0 , 1 , n , 1));
if(opt == 5) printf("%lld\n" , query(x , 1 , 1 , n , 1));
}
return 0;
}