UOJ 164 线段树历史最值

164. 【清华集训2015】V

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

这个电阻器内有编号为 1∼n1∼n 的 nn 个独立水箱，水箱呈圆柱形，底面积为 1 m21 m2，每个水箱在顶部和底部各有一个阀门，可以让水以 1 m3/s1 m3/s 的流量通过，每个水箱的上阀门接水龙头，可以无限供应水，下阀门不接东西，可以让水流出。水箱顶部和底部都有一个接口，水的电阻率为 1 Ω⋅m1 Ω⋅m。

水箱的高度足够高，有一个导电浮标浮在水面上，通过导线与水箱顶的接口相连。一开始时第 ii 个水箱中有 ai m3ai m3 的水。

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

1、打开编号在 [l,r][l,r] 中的所有水箱的上方阀门 xx 秒，然后关上它们的上方阀门。

2、打开编号在 [l,r][l,r] 中的所有水箱的下方阀门 xx 秒，然后关上它们的下方阀门。

3、将编号在 [l,r][l,r] 中的所有水箱的下方阀门与大海通过连通器以一定方式相连，使得这些水箱中都恰拥有 x m3x m3 的水，然后关上它们的下方阀门，撤去连通器。

4、在第 yy 个水箱的上下方接口处接上一个电动势为 1 V1 V 的电源，电源没有内阻，Picks博士会测量出通过电源的电流大小，之后撤去该电源。

5、由于水浸泡过的地方会留下明显的水渍而没有被水浸泡过的地方不会有，Picks博士可以据此测量出此时第 yy 个水箱的水渍高度，以推断曾经最多有多少水，节约他的建造成本。

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

第一行两个数：n,mn,m。

接下来一行 nn 个数，第 ii 个数表示初始时第 ii 个水箱内有 ai m3ai m3 的水。

接下来 mm 行中，第 ii 行第一个数 titi 表示操作类型：

若 ti=1ti=1，则接下来三个整数 li,ri,xili,ri,xi，表示打开编号在 [li,ri][li,ri] 中的所有水箱的上方接口 xixi 秒。

若 ti=2ti=2，则接下来三个整数 li,ri,xili,ri,xi，表示打开编号在 [li,ri][li,ri] 中的所有水箱的下方接口 xixi 秒。

若 ti=3ti=3，则接下来三个整数 li,ri,xili,ri,xi，表示将编号在 [li,ri][li,ri] 中的所有水箱与大海连接，使这些水箱中都恰有 xi m3xi m3 的水。

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

若 ti=5ti=5，则接下来一个整数 yiyi，表示测量此时在第 yiyi 个水箱中的水渍高度。
输出格式

对于每个 ti=4ti=4，输出一个整数表示通过电源的电流大小的倒数（单位为 A−1A−1 ），如果电流为无穷大则输出0。

对于每个 ti=5ti=5，输出一个整数表示在第 yiyi 个水箱中的水渍高度（单位为 mm ）。
样例输入一

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

样例输出一

0
3
4

样例输入二

见相关文件下载
样例输出二

见相关文件下载
样例输入三

见相关文件下载
样例输出三

见相关文件下载
限制与约定

时间限制：2s2s

空间限制：128MB128MB
测试点编号 n=n= m=m= 约定
1 10001000 10001000
2 10001000 10001000
3 105105 105105 没有操作2
4 5×1055×105 5×1055×105 没有操作2
5 105105 105105 没有操作1与操作5
6 105105 105105 没有操作1
7 5×1055×105 5×1055×105 没有操作1
8 5×1055×105 5×1055×105 没有操作5
9 105105 105105
10 5×1055×105 5×1055×105

对于所有的数据：1≤n,m≤5×105, 0≤ai,xi≤109,1≤li≤ri≤n, 1≤yi≤n1≤n,m≤5×105, 0≤ai,xi≤109,1≤li≤ri≤n, 1≤yi≤n.
提示

可能用到的物理公式：

1、欧姆定律：I=URI=UR，其中 I,U,RI,U,R 分别代表电流、电压和电阻。

2、电阻率公式：R=ρLSR=ρLS，其中 R,ρ,L,SR,ρ,L,S 分别代表电阻、电阻率、电阻长度、横截面积。

用了一个神奇的标记，网上有很多解释！！！

  1 #include<cstdio>
  2 #include<cstdlib>
  3 #include<cstring>
  4 #include<cmath>
  5 #include<iostream>
  6 #include<algorithm>
  7 
  8 using namespace std;
  9 
 10 #define lc (o<<1)
 11 #define rc (o<<1|1)
 12 #define mid ((L+R)>>1)
 13 #define LL long long
 14 #define pb push_back
 15 #define Set(a, v) memset(a, v, sizeof(a))
 16 #define For(i, a, b) for(int i = (a); i <= (int)(b); i++)
 17 #define Forr(i, a, b) for(int i = (a); i >= (int)(b); i--)
 18 
 19 #define INF (1LL<<60)
 20 #define MAXN (500000+5)
 21 
 22 void read(int &x){
 23     char ch = getchar();
 24     while(ch < '0' || ch > '9') ch = getchar();
 25 
 26     x = 0;
 27     while(ch >= '0' && ch <= '9'){
 28         x = x*10+ch-'0';
 29         ch = getchar();
 30     }
 31 }
 32 
 33 struct Tage{
 34     LL a, b, ma, mb;
 35 
 36     Tage operator +=(const Tage &tmp){
 37         Tage ret;
 38         ret.a = max(tmp.a+a, -INF); //in order to not be bombed
 39         ret.b = max(b+tmp.a, tmp.b);
 40         ret.ma = max(a+tmp.ma, ma); 
 41         ret.mb = max(mb, max(tmp.mb, b+tmp.ma));
 42 
 43         a = ret.a; b = ret.b; ma = ret.ma; mb = ret.mb;
 44     }
 45 };
 46 
 47 int ql, qr;
 48 
 49 struct Seg_tree{
 50     Tage t[MAXN*4];
 51 
 52     void build(int o, int L, int R){
 53         t[o] = (Tage){0, -INF, 0, -INF};
 54         if(L == R) return;
 55         build(lc, L, mid); build(rc, mid+1, R);
 56     }
 57 
 58     void pushdown(int o){
 59         t[lc] += t[o]; t[rc] += t[o];
 60         t[o] = (Tage){0, -INF, 0, -INF};
 61     }
 62 
 63     void modify(int o, int L, int R, Tage tag){
 64         if(ql <= L && qr >= R){
 65             t[o] += tag; return;
 66         }
 67 
 68         pushdown(o);
 69         if(ql <= mid) modify(lc, L, mid, tag);
 70         if(qr > mid) modify(rc, mid+1, R, tag);
 71     }
 72 
 73     Tage query(int o, int L, int R, int pos){ //query one node (pos)
 74         if(L == R) return t[o];
 75         pushdown(o);
 76 
 77         if(pos <= mid) return query(lc, L, mid, pos);
 78         return query(rc, mid+1, R, pos);
 79     }
 80 }ST;
 81 
 82 int main(){
 83     int n, m;
 84 
 85     read(n); read(m);
 86     ST.build(1, 1, n);
 87 
 88     For(i, 1, n){
 89         int tmp;
 90         read(tmp);
 91         ql = qr = i;
 92         ST.modify(1, 1, n, (Tage){tmp, -INF, tmp, -INF});
 93     }
 94 
 95     int type, L, R, rx;
 96     Tage ans;
 97     LL x;
 98 
 99     while(m--){
100         read(type); 
101 
102         if(type <= 3){
103             read(ql); read(qr); read(rx);
104             x = rx;
105 
106             if(type == 1) ST.modify(1, 1, n, (Tage){x, -INF, x, -INF});
107             else if(type == 2) ST.modify(1, 1, n, (Tage){-x, 0, -x, 0});
108             else ST.modify(1, 1, n, (Tage){-INF, x, -INF, x});
109         }else{
110             read(rx);
111             ans = ST.query(1, 1, n, rx);
112 
113             if(type == 4) printf("%lld\n", max(ans.a, ans.b));
114             else printf("%lld\n", max(ans.ma, ans.mb));
115         }
116     }
117 
118     return 0;
119 }

Miaomiao❤ ++RP