Link
http://www.Sina.com/http://www.Sina.com /
luogu P6242
这个大人物写得很好%%
对于每个节点，保留当前最大值、当前下一个最大值、过去最大值、过去下一个最大值、当前最大值数量、区间和四个懒惰标记。
四个懒惰标记分别如下。
(lazy1)与当前最大值相加的值lazy2)与过去的最大值相加的值lazy3)与当前的最大值以外相加的值lazy4)与过去的最大值以外相加的值相加操作)全部相加
取最小操作：考虑取的最小值Val val的差异。 VAL Val的值大于或等于当前区间的最大值，无需更新； 如果v a l val val小于最大值且在下一个大的值以上，则将更新了最大值的数量作为val val，将最大值m a x a maxa maxa的个数作为cntCNT，从区间和开始计算cnt(maxaval ) CNT * (maxa
剩下的操作是常规的分段树操作
具体看看代码吧QAQ
Description
# include iostream # include cstdio # include cstring # include algorithm # definen 500010 # definelllonglong # define INF 100000000 DD defineL3 ) k ).lazy3#defineL4) k ) t(k ).lazy4#definema ) ) t(k ).Mama ) ) k dfineCNT(k ).cnt LL lazy1、lazy2、lazy3、lazy4； LL sum； } t[N * 10]； int n，m； LL a[N]； int read () intret=0； char cc=getchar (，zf=' '； while (抄送'0)||抄送
'9') zf = cc, cc = getchar();while (cc >= '0' && cc <= '9'){ret = ret * 10 + cc - '0';cc = getchar();}if (zf == '-') return -ret;return ret;}void pushup (int k) //把儿子的信息转移更新到第k个{int y = k * 2;sum(k) = sum(y) + sum(y + 1);ma(k) = max (ma(y), ma(y + 1));mb(k) = max (mb(y), mb(y + 1));if (ma(y) == ma(y + 1)) //两边区间最大值相同 cnt(k) = cnt(y) + cnt(y + 1), p(k) = max (p(y), p(y + 1));else if (ma(y) > ma(y + 1)) cnt(k) = cnt(y), p(k) = max (ma(y + 1), p(y));else cnt(k) = cnt(y + 1), p(k) = max (ma(y), p(y + 1));}void build (int k, int l, int r){l(k) = l, r(k) = r;l1(k) = l2(k) = l3(k) = l4(k) = 0;if (l == r){sum(k) = ma(k) = mb(k) = a[l];cnt(k) = 1, p(k) = -inf;return;} //赋初值int mid = (l + r) / 2;build (k * 2, l, mid);build (k * 2 + 1, mid + 1, r);pushup (k);}void update (int k, int l1, int l2, int l3, int l4){sum(k) += (LL)(cnt(k) * l1 + (r(k) - l(k) + 1 - cnt(k)) * l3); mb(k) = max (mb(k), ma(k) + l2); //因为要考虑操作的顺序，最大的那就是之前全部操作完最大的值加上新的这段时间的历史最大值ma(k) += l1;if (p(k) != -inf) p(k) += l3;l2(k) = max (l2(k), l1(k) + l2); //同上l4(k) = max (l4(k), l3(k) + l4);l1(k) += l1, l3(k) += l3;}void pushdown (int k){if (!l1(k) && !l2(k) && !l3(k) && !l4(k)) return;int y = k * 2, maxn = max (ma(y), ma(y + 1));if (ma(y) == maxn) update (y, l1(k), l2(k), l3(k), l4(k));else update (y, l3(k), l4(k), l3(k), l4(k));if (ma(y + 1) == maxn) update (y + 1, l1(k), l2(k), l3(k), l4(k));else update (y + 1, l3(k), l4(k), l3(k), l4(k)); //分最大值是否在区间内两种情况进行处理（不在的话都看作非最大值处理l1(k) = l2(k) = l3(k) = l4(k) = 0;}void add (int k, int ll, int rr, LL val){pushdown (k);if (ll <= l(k) && r(k) <= rr){update (k, val, val, val, val); //全加上return;}int mid = (l(k) + r(k)) / 2;if (ll <= mid) add (k * 2, ll, rr, val);if (mid + 1 <= rr) add (k * 2 + 1, ll, rr, val);pushup (k);}void newmin (int k, int ll, int rr, LL val){pushdown (k);if (ma(k) <= val) return;if (ll <= l(k) && r(k) <= rr && p(k) <= val){update (k, val - ma(k), val - ma(k), 0, 0);return;}int mid = (l(k) + r(k)) / 2;if (ll <= mid) newmin (k * 2, ll, rr, val);if (mid + 1 <= rr) newmin (k * 2 + 1, ll, rr, val);pushup (k);}LL asksum (int k, int ll, int rr){pushdown (k);if (ll <= l(k) && r(k) <= rr) return sum(k);LL ret = 0; int mid = (l(k) + r(k)) / 2;if (ll <= mid) ret += asksum (k * 2, ll, rr);if (mid + 1 <= rr) ret += asksum (k * 2 + 1, ll, rr);pushup (k);return ret;}LL askma (int k, int ll, int rr){pushdown (k);if (ll <= l(k) && r(k) <= rr) return ma(k);int mid = (l(k) + r(k)) / 2;LL ret = -inf;if (ll <= mid) ret = max (ret, askma (k * 2, ll, rr));if (mid + 1 <= rr) ret = max (ret, askma (k * 2 + 1, ll, rr));pushup (k);return ret;}LL askmb (int k, int ll, int rr){pushdown (k);if (ll <= l(k) && r(k) <= rr) return mb(k);int mid = (l(k) + r(k)) / 2;LL ret = -inf;if (ll <= mid) ret = max (ret, askmb (k * 2, ll, rr));if (mid + 1 <= rr) ret = max (ret, askmb (k * 2 + 1, ll, rr));return ret;}int main(){for (int i = 0; i < N * 10; i++) ma(i) = mb(i) = p(i) = -inf;n = read(), m = read();for (int i = 1; i <= n; i++) a[i] = read();build (1, 1, n);int type, l, r, x;for (int i = 1; i <= m; i++){type = read(), l = read(), r = read();if (type == 1) x = read(), add (1, l, r, x);else if (type == 2) x = read(), newmin (1, l, r, x);else if (type == 3) printf ("%lldn", asksum (1, l, r));else if (type == 4) printf ("%lldn", askma (1, l, r));else printf ("%lldn", askmb (1, l, r));}return 0;}