【uoj#164】[清华集训2015]V 线段树维护历史最值

题目描述

给你一个长度为 $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;

}