「UOJ 164」「清华集训2015」V

UOJ #164

题意

给出一个长度为$n$的数列$a$，需要维护以下操作

1. 对于$i\in[l,r]$，$a_i=a_i+x$

2. 对于$i\in[l,r]$，$a_i=max(a_i-x,0)$

3. 对于$i\in[l,r]$，$a_i=x$

4. 询问$a_y$

5. 询问$a_y$的历史最大值

$n,m\le 5*10^5,0\le a_i,x\le10^9$

---

分析

定义标记$(x,y)$表示先$+x$再对$y$取$max$

前三种操作可以转化为

1. $(x,0)$
2. $(-x,0)$
3. $(-inf,x)$

标记是可以合并的。把时间较晚的$(c,d)$合并到$(a,b)$上，得到标记$(a+c,max(b+c,d))$

每个节点维护标记$(add,mx)$，和上次$pushdown$该节点之后到现在，标记两部分的历史最大值$(madd,mmx)$

带历史最大值标记的下传具体参考代码

每次查询下传到底就好了

注意$add$标记$-inf$时不要爆了

时间复杂度 $\mathcal O(m\log n)$

---

代码

#include<cstdio>
#include<algorithm>
#include<ctype.h>
#include<string.h>
#include<math.h>

using namespace std;
#define ll long long

inline char read() {
	static const int IN_LEN = 1000000;
	static char buf[IN_LEN], *s, *t;
	return (s == t ? t = (s = buf) + fread(buf, 1, IN_LEN, stdin), (s == t ? -1 : *s++) : *s++);
}
template<class T>
inline void read(T &x) {
	static bool iosig;
	static char c;
	for (iosig = false, c = read(); !isdigit(c); c = read()) {
		if (c == '-') iosig = true;
		if (c == -1) return;
	}
	for (x = 0; isdigit(c); c = read()) x = ((x + (x << 2)) << 1) + (c ^ '0');
	if (iosig) x = -x;
}
const int OUT_LEN = 10000000;
char obuf[OUT_LEN], *ooh = obuf;
inline void print(char c) {
	if (ooh == obuf + OUT_LEN) fwrite(obuf, 1, OUT_LEN, stdout), ooh = obuf;
	*ooh++ = c;
}
template<class T>
inline void print(T x) {
	static int buf[30], cnt;
	if (x == 0) print('0');
	else {
		if (x < 0) print('-'), x = -x;
		for (cnt = 0; x; x /= 10) buf[++cnt] = x % 10 + 48;
		while (cnt) print((char)buf[cnt--]);
	}
}
inline void flush() { fwrite(obuf, 1, ooh - obuf, stdout); }

const int N = 500005;
const ll inf = 1e16;
int n, m, a[N];
ll add[N<<2], madd[N<<2], mx[N<<2], mmx[N<<2];
inline void chkmx(ll &x, ll y){ x<y?x=y:0;}
inline void pushdown(int t){
	int k=t<<1;
	chkmx(madd[k], add[k]+madd[t]);
	chkmx(mmx[k], max(mmx[t], mx[k]+madd[t]));
	chkmx(add[k]+=add[t], -inf);
	mx[k]=max(mx[t], mx[k]+add[t]);
	chkmx(madd[k|1], add[k|1]+madd[t]);
	chkmx(mmx[k|1], max(mmx[t], mx[k|1]+madd[t]));
	chkmx(add[k|1]+=add[t], -inf);
	mx[k|1]=max(mx[t], mx[k|1]+add[t]);
	add[t]=madd[t]=mx[t]=mmx[t]=0;
}
void build(int l, int r, int t){
	if(l==r) return (void)(add[t]=madd[t]=a[l]);
	int mid=l+r>>1, k=t<<1;
	build(l, mid, k), build(mid+1, r, k|1);
}
void change(int l, int r, int t, int L, int R, ll x, ll y){
	if(L<=l && r<=R) return chkmx(madd[t], add[t]+=x), chkmx(mmx[t], mx[t]=max(mx[t]+x, y));
	int mid=l+r>>1, k=t<<1;
	pushdown(t);
	if(L<=mid) change(l, mid, k, L, R, x, y);
	if(R>mid) change(mid+1, r, k|1, L, R, x, y);
}
ll query(int l, int r, int t, int pos, bool opt){
	if(l==r) return opt?max(madd[t], mmx[t]):max(add[t], mx[t]);
	int mid=l+r>>1, k=t<<1;
	pushdown(t);
	return pos<=mid?query(l, mid, k, pos, opt):query(mid+1, r, k|1, pos, opt);
}
int main() {
	read(n), read(m);
	for(int i=1; i<=n; ++i) read(a[i]);
	build(1, n, 1);
	while(m--){
		static int opt, l, r, x;
		read(opt), read(l);
		if(opt<=3){
			read(r), read(x);
			if(opt==1) change(1, n, 1, l, r, x, 0);
			else if(opt==2) change(1, n, 1, l, r, -x, 0);
			else change(1, n, 1, l, r, -inf, x);
		}
		else print(query(1, n, 1, l, opt-4)), print('\n');
	}
	return flush(), 0;
}