洛谷P4314 CPU 监控题解

题意：

维护一个数据结构，支持

询问区间最大值。

询问区间历史最大值。

区间加法。

区间赋值。

数据范围：

\(1\le T,E\le 10^5,~1\le X\le Y\lt T,~-2^{31}\leq Z\lt 2^{31}\)。

对于每个结点，我们需要维护 \(6 + 1\) 个值，分别对应

加法标记、历史最大加法标记、赋值标记、历史最大赋值标记、最大值、历史最大值、是否存在赋值标记。

肯定有人和我一样好奇为什么要维护历史最大的标记。

因为修改是基于标记的修改，当标记下传时可能不是历史最大值对应的标记。

打个比方，区间 \(+1\) 再 \(-1\) 。加法标记变成了 \(0\) ，但是我们历史最大加法标记应当是 \(1\) ，历史最大值应为 \(1\) 。

接下来就是维护的细节了。

\(\mathtt{push\_up}\) 函数比较简单，就是合并一下最大值和历史最大值。

询问和修改也没啥特别的，主要难在 \(\mathtt{push\_down}\) 函数。

首先搞清楚我们的标记处理顺序：先赋值后加。

也就是存在赋值标记时，加法是在赋值标记上加的。否则就是正常的加法标记。

原理明白了，就没啥好说的了，直接看代码即可。

时间复杂度 \(\mathcal{O}(n \log n)\)

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define ls(at) ((at) << 1)
#define rs(at) ((at) << 1 | 1)
#define N ((int)(1e5+15))
#define N4 (N * 4)

bitset<N4> vis;
int sum1[N4],sum2[N4],val1[N4],val2[N4],mx1[N4],mx2[N4];
void push_up(int at)
{
    up(mx1[at] = mx1[ls(at)], mx1[rs(at)]);
    up(mx2[at] = mx2[ls(at)], mx2[rs(at)]);
}
void build(int l,int r,int at)
{
    if(l == r) { return cin >> mx1[at], mx2[at] = mx1[at], void(0); }
    int mid = (l + r) >> 1;
    build(l,mid,ls(at)); build(mid+1,r,rs(at));
    push_up(at);
}
void proc1(int k,int max_k,int at)
{
    if(vis[at])
    {
        up(val2[at], val1[at] + max_k); up(mx2[at], mx1[at] + max_k);
        mx1[at] += k; val1[at] += k;
    }else
    {
        up(sum2[at], sum1[at] + max_k); up(mx2[at], mx1[at] + max_k);
        mx1[at] += k; sum1[at] += k;
    }
}
void proc2(int k,int max_k,int at)
{
    if(vis[at])
    {
        up(val2[at], max_k); up(mx2[at], max_k);
    }else
    {
        vis[at] = 1; val2[at] = max_k;
        up(mx2[at], max_k);
    }
    mx1[at] = val1[at] = k;
}
void push_down(int at)
{
    proc1(sum1[at], sum2[at], ls(at));
    proc1(sum1[at], sum2[at], rs(at));
    sum1[at] = sum2[at] = 0;
    if(vis[at])
    {
        proc2(val1[at], val2[at], ls(at));
        proc2(val1[at], val2[at], rs(at));
        vis[at] = val1[at] = val2[at] = 0;
    }
}
void update1(int nl,int nr,int l,int r,int k,int at)
{
    if(nl <= l && r <= nr) return proc1(k,k,at), void(0);
    push_down(at);
    int mid = (l + r) >> 1;
    if(nl <= mid) update1(nl,nr,l,mid,k,ls(at));
    if(nr > mid) update1(nl,nr,mid+1,r,k,rs(at));
    push_up(at);
}
void update2(int nl,int nr,int l,int r,int k,int at)
{
    if(nl <= l && r <= nr) return proc2(k,k,at), void(0);
    push_down(at);
    int mid = (l + r) >> 1;
    if(nl <= mid) update2(nl,nr,l,mid,k,ls(at));
    if(nr > mid) update2(nl,nr,mid+1,r,k,rs(at));
    push_up(at);
}
int query1(int nl,int nr,int l,int r,int at)
{
    if(nl <= l && r <= nr) return mx1[at];
    push_down(at);
    int mid = (l + r) >> 1;
    if(nl > mid) return query1(nl,nr,mid+1,r,rs(at));
    if(nr <= mid) return query1(nl,nr,l,mid,ls(at));
    return max(query1(nl,nr,l,mid,ls(at)), query1(nl,nr,mid+1,r,rs(at)));
}
int query2(int nl,int nr,int l,int r,int at)
{
    if(nl <= l && r <= nr) return mx2[at];
    push_down(at);
    int mid = (l + r) >> 1;
    if(nl > mid) return query2(nl,nr,mid+1,r,rs(at));
    if(nr <= mid) return query2(nl,nr,l,mid,ls(at));
    return max(query2(nl,nr,l,mid,ls(at)), query2(nl,nr,mid+1,r,rs(at)));
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    int n,q,x,y,z; char ch;
    cin >> n; build(1,n,1); cin >> q;
    for(; q; q--)
    {
        cin >> ch >> x >> y;
        switch(ch)
        {
            case 'Q' : cout << query1(x,y,1,n,1) << '\n'; break; // 最大值
            case 'A' : cout << query2(x,y,1,n,1) << '\n'; break; // 历史最大值
            case 'P' : cin >> z; update1(x,y,1,n,z,1); break; // 加法
            case 'C' : cin >> z; update2(x,y,1,n,z,1); break; // 赋值
            default: assert(isalpha(ch)); break;
        }
    }
    return 0;
}