参考
关键是加一个标记cv：这个区间有多少个结点，已被 tag 影响。
Gorgeous SequenceTime Limit: 6000/3000 MS (Java/Others)Memory Limit: 131072/131072 K (Java/Others)Total Submission(s): 396Accepted Submission(s): 78
Problem Description
There is a sequenceof length. We useto denote the-th element in this sequence. You should do the following three types of operations to this sequence.: For every, we useto replace the original’s value.: Print the maximum value of.: Print the sum of.
Input
The first line of the input is a single integer, indicating the number of testcases.The first line contains two integersdenoting the length of the sequence and the number of operations.The second line containsseparated integers).Each of the followinglines represents one operation ().It is guaranteed that.
Output
For every operation of type, print one line containing the answer to the corresponding query.
Sample Input
15 51 2 3 4 51 1 52 1 50 3 5 31 1 52 1 5
Sample Output
515312
Hint
Please use efficient IO method
Source
#include <bits/stdc++.h>using namespace std;typedef long long ll;#define prt(k) cout<<#k" = "<<k<<" ";const int N = 1000003<<2;struct Node{int l, r;int mx;ll ss;int tag;int cv; /// How many nodes are infected by tag in subtree} T[N] ;int a[N];#define lx x<<1#define rx x<<1|1#define lo o<<1#define ro o<<1|1/// cv：这个区间有多少个结点，已被 tag 影响。void pushup(int x){T[x].ss = T[lx].ss + T[rx].ss;T[x].mx = max(T[lx].mx, T[rx].mx);T[x].cv = T[lx].cv + T[rx].cv;}void mark(int x, int t) /// da biao ji{if (T[x].tag!=0 && T[x].tag <= t) return ;T[x].tag = t;int l = T[x].l, r = T[x].r;if (T[x].cv != r – l + 1){T[x].mx = t;T[x].ss += 1ll * (r – l + 1 – T[x].cv) * t;T[x].cv = r – l + 1;}}void pushdown(int x){if (T[x].tag==0) return;mark(lx, T[x].tag);mark(rx, T[x].tag);}void fix(int o, int t ){if (T[o].mx < t) return;if (T[o].tag >= t){T[o].tag = 0; ///}if (T[o].l==T[o].r){T[o].ss = T[o].mx = T[o].tag;T[o].cv = T[o].tag != 0;}else{pushdown(o);fix(lo, t);fix(ro, t);pushup(o);}}void update(int o, int t , int L, int R){if (T[o].mx <= t) return;if (R < T[o].l || T[o].r < L ) return;if (L<=T[o].l && T[o].r<=R){fix(o, t);if (T[o].l == T[o].r){T[o].ss = T[o].mx= T[o].tag = t;T[o].cv = 1;}else{pushup(o);}mark(o, t);}else{pushdown(o);update(o<<1, t, L, R);update(o<<1|1, t, L, R);pushup(o);}}void build(int o, int l, int r){T[o].l = l;T[o].r = r;if (l==r){T[o].ss = T[o].mx = T[o].tag = a[l];T[o].cv = 1;return;}int m = (l + r) >> 1;T[o].tag = 0;build(lo, l, m);build(ro, m+1, r);pushup(o);}Node query(int o, int L, int R){Node ret ;if (L > T[o].r || R < T[o].l){ret.mx = ret.ss = 0;return ret;}if (L<=T[o].l && T[o].r <= R) return T[o];pushdown(o);Node a = query(lo, L, R);Node b = query(ro, L, R);ret.mx = max(a.mx, b.mx);ret.ss = a.ss + b.ss;return ret;}/************Read**********/char *ch, *ch1, buf[40*1024000+5], buf1[40*1024000+5];void read(int &x){for (++ch; *ch <= 32; ++ch);for (x = 0; '0' <= *ch; ch++) x = x * 10 + *ch – '0';}/**************************/int n, m;int main(){ch = buf – 1;ch1 = buf1 – 1;fread(buf, 1, 1000 * 35 * 1024, stdin);int re;read(re);while (re–){read(n);read(m);for (int i = 1; i <= n; i++)read(a[i]);build(1 , 1, n);while (m–){int t, x, y, z;read(t);read(x);read(y);if (!t){read(z);update(1, z, x, y);}else if (t == 1) printf("%d\n", query(1, x, y).mx);else printf("%I64d\n", query(1, x, y).ss);}}return 0;}/**15 51 2 3 4 51 1 52 1 50 3 5 31 1 52 1 5*/
版权声明：本文为博主原创文章，未经博主允许不得转载。
，任何的限制，都是从自己的内心开始的。
