UOJ - 164

Posted by WildCow on April 12, 2018

[清华集训2015]V

Time Limit: 2000ms
Memory Limit: 128mb

Description

Picks博士观察完金星凌日后,设计了一个复杂的电阻器。为了简化题目,题目中的常数与现实世界有所不同。

这个电阻器内有编号为 $1∼n$ 的 $n$ 个独立水箱,水箱呈圆柱形,底面积为 $1{m}^2$,每个水箱在顶部和底部各有一个阀门,可以让水以 $1{m}^3/s$ 的流量通过,每个水箱的上阀门接水龙头,可以无限供应水,下阀门不接东西,可以让水流出。水箱顶部和底部都有一个接口,水的电阻率为 $1Ω\cdot m$。

水箱的高度足够高,有一个导电浮标浮在水面上,通过导线与水箱顶的接口相连。一开始时第 $i$ 个水箱中有 $a_i {m}^3$ 的水。

Picks博士接下来就需要对这个复杂的电阻器进行调试。他会进行以下五种操作。

  • 打开编号在 $[l, r]$ 中的所有水箱的上方阀门 $x$ 秒,然后关上它们的上方阀门。
  • 打开编号在 $[l, r]$ 中的所有水箱的下方阀门 $x$ 秒,然后关上它们的下方阀门。
  • 将编号在 $[l, r]$ 中的所有水箱的下方阀门与大海通过连通器以一定方式相连,使得这些水箱中都恰拥有 $x {m}^3$ 的水,然后关上它们的下方阀门,撤去连通器。
  • 在第 $y$ 个水箱的上下方接口处接上一个电动势为 $1 V$ 的电源,电源没有内阻,Picks博士会测量出通过电源的电流大小,之后撤去该电源。
  • 由于水浸泡过的地方会留下明显的水渍而没有被水浸泡过的地方不会有,Picks博士可以据此测量出此时第 $y$ 个水箱的水渍高度,以推断曾经最多有多少水,节约他的建造成本。

现在,他请你来帮他做预实验,你能告诉他每次测量得到的电流大小以及测量得到的最多的水量是多少吗?

Input

第一行两个数:$n,m$。

接下来一行 $n$ 个数,第 $i$ 个数表示初始时第 $i$ 个水箱内有 $a_i {m}^3$ 的水。

接下来 $m$ 行中,第 $i$ 行第一个数 $t_i$ 表示操作类型:

若 $t_i=1$,则接下来三个整数 $l_i,r_i,x_i$,表示打开编号在 $[l, r]$ 中的所有水箱的上方接口 $xi$ 秒。

若 $t_i=2$,则接下来三个整数 $l_i,r_i,x_i$,表示打开编号在 $[l, r]$ 中的所有水箱的下方接口 $xi$ 秒。

若 $t_i=3$,则接下来三个整数 $l_i,r_i,x_i$,表示将编号在 $[l, r]$ 中的所有水箱与大海连接,使这些水箱中都恰有 $x {m}^3$ 的水。

若 $t_i=4$,则接下来一个整数 $y_i$,表示测量在第 $y_i$ 个水箱的上下方接口处接上一个电动势为 $1 V$ 的电源时通过电源的电流。

若 $t_i=5$,则接下来一个整数 $y_i$,表示测量此时在第 $y_i$ 个水箱中的水渍高度。

对于所有的数据:$1≤n,m≤5×10^5, 0≤ai,xi≤10^9,1≤li≤ri≤n, 1≤yi≤n1≤n,m≤5×10^5, 0≤ai,xi≤10^9,1≤li≤ri≤n, 1≤yi≤n$。

Output

对于每个 $t_i=4$,输出一个整数表示通过电源的电流大小的倒数(单位为 ${A}^{−1}$ ),如果电流为无穷大则输出 0。

对于每个 $t_i=5$,输出一个整数表示在第 $y_i$ 个水箱中的水渍高度(单位为 $mm$ )。

Sample Input

5 6
1 2 3 4 5
2 1 3 2
4 1
1 1 4 1
5 3
3 1 5 4
4 2

Sample Output

0
3
4

Hint

可能用到的物理公式:

  • 欧姆定律:$I=\frac{U}{R}$,其中 $I,U,R$ 分别代表电流、电压和电阻。
  • 电阻率公式:$R=ρ\frac{L}{S}$,其中 $R,ρ,L,S$ 分别代表电阻、电阻率、电阻长度、横截面积。

这样的题目

估计看到题目

就没人想做了

让我们用人话重新说一下题目

对于一个数列

你有 5 种操作

  • 区间加
  • 区间减,将减得到的结果与 0 取 max
  • 区间赋值
  • 查当前单点的值
  • 查单点历史最值

历史最值没办法用延迟标记

有可能一个标记还未被传下去用于更新实际数值就被另一个标记覆盖了

所以暴力去用线段树维护对于单次区间更新会退化到 $nlog{(n)}$

所以我们考虑维护延迟标记二元组 $(a, b)$

表示 $x = max(x + a, b)$

于是前三种操作能统一:

  • 加法:$(x, 0)$
  • 减法:$(-x, 0)$
  • 区间赋值:$(-INF, x)$

然后对线段树每个节点

维护 $a, b, ma, mb$ 四个延迟标记

分别表示当前值的二元组$(a, b)$ 的累加以及历史二元组$(ma, mb)$ 的最值

然后考虑二元组的累加,即 down 操作

如果有新标记 $a′,b′$ 要加到原有标记上

那么显然有 $x’ = max(max(x+a,b)+a′,b′)$

然后随便化简一下

即 $x’ = max(x+a+a′,max(b+a′,b′))$

这样能用一个新的二元组 $(a + a’, max(b + a’, b’))$ 来表示了

所以当我们把 $a’,b’,ma’,mb’$ 传下去的时候

对于他子节点的 $a,b,ma,mb$

有 :

  • $ma = max(ma, a+ ma’)$
  • $mb = max(mb, max(b+ma′,mb′))$
  • $a = max(a + a’, -INF)$,这边和 -INF 取 max 是为了防止多次进行 -INF 的计算最后爆掉
  • $b = max(b + a’, b’)$

同时down 的顺序要和上面写的顺序相同

这个能搓出来最后就很好写代码了


#include <bits/stdc++.h>
#define LL long long
using namespace std;

const LL INF = (1ll * 1) << 60;
const int N = 500050;

struct Tree
{
    int l;
    int r;
    LL na;
    LL nb;
    LL pa;
    LL pb;
};

Tree teee[N << 2];
int n, m;
LL ma[N];

void down(int x)
{
    tree[x << 1].pa = max(tree[x << 1].pa, tree[x].pa + tree[x << 1].na);
    tree[x << 1].pb = max(tree[x << 1].pb, max(tree[x].pb, tree[x << 1].nb + tree[x].pa));
    tree[x << 1].na = max(tree[x << 1].na + tree[x].na, -INF);
    tree[x << 1].nb = max(tree[x << 1].nb + tree[x].na, tree[x].nb);
    tree[x << 1 | 1].pa = max(tree[x << 1 | 1].pa, tree[x].pa + tree[x << 1 | 1].na);
    tree[x << 1 | 1].pb = max(tree[x << 1 | 1].pb, max(tree[x].pb, tree[x << 1 | 1].nb + tree[x].pa));
    tree[x << 1 | 1].na = max(tree[x << 1 | 1].na + tree[x].na, -INF);
    tree[x << 1 | 1].nb = max(tree[x << 1 | 1].nb + tree[x].na, tree[x].nb);
    tree[x].na = tree[x].nb = tree[x].pa = tree[x].pb = 0;
}
    
void build(int x, int l, int r)
{
    tree[x].l = l;
    tree[x].r = r;
    if(l == r){
        tree[x].na = tree[x].pa = ma[l];
    }
    else{
        int mid;

        mid = l + ((r - l) >> 1);
        build(x << 1, l, mid);
        build(x << 1 | 1, mid + 1, r);
    }
}

void update(int x, int l, int r, int a, int b)
{
    int ll, rr;

    ll = tree[x].l;
    rr = tree[x].r;
    if(l > r){
        return ;
    }
    if(ll == l && rr == r){
        tree[x].na = max(tree[x].na + a, -INF);
        tree[x].nb = max(tree[x].nb + a, b);
        tree[x].pa = max(tree[x].pa, tree[x].na);
        tree[x].pb = max(tree[x].pb, tree[x].nb);
    }
    else{
        int mid;

        mid = ll + ((rr - ll) >> 1);
        donw(x);
        update(x << 1, l, min(mid, r), a, b);
        update(x << 1 | 1, max(mid + 1, l), r, a, b);
    }
}

LL quary1(int x, int l, int r);
{
    int ll, rr;

    ll = tree[x].l;
    rr = tree[x].r;
    if(l > r){
        return -INF;
    }
    if(ll == l && rr == r){
        return max(na[x], nb[x]);
    }
    else{
        int mid;
        int ans;

        ans = -INF;
        mid = ll + ((rr - ll) >> 1);
        donw(x);
        ans = max(ans, update(x << 1, l, min(mid, r)));
        ans = max(ans, update(x << 1 | 1, max(mid + 1, l), r));

        return ans;
    }
}

LL quary2(int x, int l, int r);
{
    int ll, rr;

    ll = tree[x].l;
    rr = tree[x].r;
    if(l > r){
        return -INF;
    }
    if(ll == l && rr == r){
        return max(pa[x], pb[x]);
    }
    else{
        int mid;
        int ans;

        ans = -INF;
        mid = ll + ((rr - ll) >> 1);
        donw(x);
        ans = max(ans, update(x << 1, l, min(mid, r)));
        ans = max(ans, update(x << 1 | 1, max(mid + 1, l), r));

        return ans;
    }
}

int main(int argc, char const *argv[])
{
    while(scanf("%d%d", &n, &m) == 2){
        for(int i = 1; i <= n; i ++){
            scanf("%lld", &ma[i]);
        }
        build(1, 1, n);
        for(int i = 0; i < m; i ++){
            int x;
            int l, r, t;

            scanf("%d", &x);
            if(x == 1){
                scanf("%d%d%d", &l, &r, &t);
                update(1, l, r, t, 0);
            }
            else if(x == 2){
                scanf("%d%d%d", &l, &r, &t);
                update(1, l, r, -t, 0);
            }
            else if(x == 3){
                scanf("%d%d%d", &l, &r, &t);
                update(1, l, r, -INF, x);
            }
            else if(x == 4){
                scanf("%d", &l);
                printf("%lld\n", quary1(1, l, l));
            }
            else{
                scanf("%d", &l);
                printf("%lld\n", quary2(1, l, l));
            }
        }
    }


    return 0;
}