「清华集训2015」V

「清华集训2015」V

题目大意:

你有一个序列，你需要支持区间加一个数并对 (0) 取 (max)，区间赋值，查询单点的值以及单点历史最大值。

解题思路：

观察发现，每一种修改操作都可以用一个函数 (f(x) = max(x+a,b)) 来表示。

操作 1： (f(x) = (x,0))。

操作 2：(f(x)=(-x, 0))。

操作 (3)：(f(x)=-(inf,0))。

这东西显然满足结合律，事实上还是封闭的

[f1(f2(x)) = max(max(x+f2a,f2b)+f1a,f1b) \ =max(x+f2a+f1a,f2b+f1a,f1b) \ =max(x+f1a+f2a,max(f1a+f2b,f1b)) ]

然后每一次操作把函数当做标记打在线段树对应节点上，直接合并标记就可以做单点查询了。注意这里合并有先后顺序，显然儿子的标记的时间一定早于父亲的标记，不然就被 ( ext{pushdown}) 了，那么只要令儿子的标记为 (f2) ，父亲的标记为 (f1) 这样合并就好了。

考虑求历史最大值，本质上是要维护每一个节点从上一次下放到当前所有时刻标记的最大值，每次下放标记的时候维护儿子的答案即可。历史最大值也看成 (max(x+a,b)) 的形式维护就好了。

[f1(f2(x))=max(x+max(f1a,f1a),max(f1b,f2b)) ]

####code

/*program by mangoyang*/ 
#include<bits/stdc++.h>
#define inf ((ll)(1e17))
#define Max(a, b) ((a) > (b) ? (a) : (b))
#define Min(a, b) ((a) < (b) ? (a) : (b))
typedef long long ll;
using namespace std;
template <class T>
inline void read(T &x){
    int ch = 0, f = 0; x = 0;
    for(; !isdigit(ch); ch = getchar()) if(ch == '-') f = 1;
    for(; isdigit(ch); ch = getchar()) x = x * 10 + ch - 48;
    if(f) x = -x;
}

#define pii pair<int, int>
#define int ll
#define fi first
#define se second

const int N = 500005;
int a[N], n, m;
pii max(pii A, pii B){
	return make_pair(max(A.fi, B.fi), max(A.se, B.se));
}
pii operator + (pii A, pii B){
	pii C = make_pair(max(A.fi + B.fi, -inf), max(A.se + B.fi, B.se));
	return C;
}
namespace Seg{
	#define lson (u << 1)
	#define rson (u << 1 | 1)
	#define mid ((l + r) >> 1)
	pii tag[N<<2], his[N<<2];
	inline void pushdown(int u){
		if(!tag[u].fi && !tag[u].se) return;
		his[lson] = max(his[lson], tag[lson] + his[u]);
		his[rson] = max(his[rson], tag[rson] + his[u]);
		tag[lson] = tag[lson] + tag[u], tag[rson] = tag[rson] + tag[u];
		tag[u] = make_pair(0ll, 0ll), his[u] = make_pair(0, 0);
	}
	inline void change(int u, int l, int r, int L, int R, pii x){	
		if(l >= L && r <= R){
			tag[u] = tag[u] + x, his[u] = max(his[u], tag[u]);
			return;
		}
		pushdown(u);
		if(L <= mid) change(lson, l, mid, L, R, x);
		if(mid < R) change(rson, mid + 1, r, L, R, x);
	}
	inline pii query(int u, int l, int r, int pos, int x){
		if(l == r) return x ? his[u] : tag[u];
		pushdown(u);
		return pos <= mid ? query(lson, l, mid, pos, x) : query(rson, mid + 1, r, pos, x);
	}
}
signed main(){
	read(n), read(m);
	for(int i = 1; i <= n; i++) read(a[i]);
	for(int i = 1, op, l, r, x; i <= m; i++){
		read(op);
		if(op == 1){ 
            read(l), read(r), read(x);
            Seg::change(1, 1, n, l, r, make_pair(x, 0ll));
        }
        if(op == 2){
            read(l), read(r), read(x);
            Seg::change(1, 1, n, l, r, make_pair(-x, 0ll));
        }
        if(op == 3){
            read(l), read(r), read(x);
            Seg::change(1, 1, n, l, r, make_pair(-inf, x));
        }
        if(op >= 4){
			read(x); pii now = Seg::query(1, 1, n, x, op == 5);
			printf("%lld
", max(a[x] + now.fi, now.se));
		}
	}
	return 0;
}