题目链接

UOJ #164

题解

首先，这道题有三种询问：区间加、区间减（减完对\(0\)取\(\max\)）、区间修改。

可以用一种标记来表示——标记\((a, b)\)表示把原来的值加上\(a\)后对\(b\)取\(\max\)。

那么区间加\(x\)就是\((x, -\infty)\)，区间减\(x\)就是\((-x, 0)\)， 区间修改就是\((-\infty, x)\)。

然后，这道题有两个询问，一个询问当前值，一个询问历史最大值，于是我们打两种不同的标记，分别维护两个询问的答案：\((a_0, b_0)\)表示当前，\((a_1, b_1)\)表示历史最大值。

下面的问题就是如何下放标记（默认\((a, b)\)是原有的，\((c, d)\)是后来加上的）。

合并\((a_0, b_0)\)和\((c_0, d_0)\)：\((a_0 + c_0, \max(b_0 + c_0, d_0))\)

合并\((a_1, b_1)\)和\((c_1, d_1)\)：\((\max(a_1, a_0 + c_1), \max(b_1, b_0 + c_1, d_1))\)

然后就可以写了 = =

#include <cstdio>

#include <cstring>

#include <cmath>

#include <algorithm>

#include <iostream>

#include <vector>

#define space putchar(' ')

#define enter putchar('\n')

typedef long long ll;

using namespace std;

template <class T>

void read(T &x){

    char c;

    bool op = 0;

    while(c = getchar(), c < '0' || c > '9')

	if(c == '-') op = 1;

    x = c - '0';

    while(c = getchar(), c >= '0' && c <= '9')

	x = x * 10 + c - '0';

    if(op) x = -x;

}

template <class T>

void write(T x){

    if(x < 0) putchar('-'), x = -x;

    if(x >= 10) write(x / 10);

    putchar('0' + x % 10);

}

const int N = 500005;

const ll INF = 1e18;

int n, m;

ll a[4*N][2], b[4*N][2], val[N];

void upt(int k){

    a[k][1] = max(a[k][1], a[k][0] + a[k >> 1][1]);

    b[k][1] = max(b[k][1], max(b[k][0] + a[k >> 1][1], b[k >> 1][1]));

    a[k][0] = max(a[k][0] + a[k >> 1][0], -INF);

    b[k][0] = max(b[k][0] + a[k >> 1][0], b[k >> 1][0]);

}

void pushdown(int k){

    upt(k << 1), upt(k << 1 | 1);

    a[k][0] = a[k][1] = 0, b[k][0] = b[k][1] = -INF;

}

void change(int k, int l, int r, int ql, int qr, ll x, ll y){

    if(ql <= l && qr >= r){

	a[k][1] = max(a[k][1], (a[k][0] + x));

	b[k][1] = max(b[k][1], max(b[k][0] + x, y));

	a[k][0] = max(a[k][0] + x, -INF);

	b[k][0] = max(b[k][0] + x, y);

	return;

    }

    pushdown(k);

    int mid = (l + r) >> 1;

    if(ql <= mid) change(k << 1, l, mid, ql, qr, x, y);

    if(qr > mid) change(k << 1 | 1, mid + 1, r, ql, qr, x, y);

}

ll query(int k, int l, int r, int p, int o){

    if(l == r) return max(val[l] + a[k][o], b[k][o]);

    pushdown(k);

    int mid = (l + r) >> 1;

    if(p <= mid) return query(k << 1, l, mid, p, o);

    else return query(k << 1 | 1, mid + 1, r, p, o);

}

int main(){

    read(n), read(m);

    for(int i = 1; i <= n; i++) read(val[i]);

    int op, l, r;

    ll x;

    while(m--){

	read(op);

	if(op <= 3){

	    read(l), read(r), read(x);

	    if(op == 1) change(1, 1, n, l, r, x, -INF);

	    if(op == 2) change(1, 1, n, l, r, -x, 0);

	    if(op == 3) change(1, 1, n, l, r, -INF, x);

	}

	else read(x), write(query(1, 1, n, x, op - 4)), enter;

    }

    return 0;

}