hdu5306 ： http://acm.hdu.edu.cn/showproblem.php?pid=5306

終于A了，暴力版線段樹

重要思想就是維護(hù)最值的時候另外維護(hù)一個次值，當(dāng)修改值介于次值和最值的時候，可以直接修改最值，而無需向下更新

#include <algorithm> #include <iostream> #include <iterator> #include <queue> #include <vector> #include <map> #include <set> #include <cmath> #include <cctype> #include <cstdio> #include <cstring> using namespace std; #define sd(x) scanf("%d",&(x)) #define sld(x) scanf("%ld",&(x)) #define slld(x) scanf("%lld",&(x)) #define sf(x) scanf("%f",&(x)) #define slf(x) scanf("%lf",&(x)) #define ss(x) scanf("%s",(x)) #define lson(x) ((x)<<1) #define rson(x) ((x)<<1|1) typedef long long ll; typedef unsigned long long ull; typedef long double real; typedef pair<int, int> pll; const real PI = acos(-1);const int maxn = 1e6 + 100; struct Node {ll mav, mavsum, miv;/*最大值， 最大值數(shù)量，次大值*/ll sum;/*子樹求和*/ }arr[maxn <<2]; ll ql, qr, qval;void pushup(int x) {int l = lson(x);int r = rson(x);arr[x].mav = max(arr[l].mav, arr[r].mav);arr[x].sum = arr[l].sum + arr[r].sum;arr[x].miv = max(arr[l].miv, arr[r].miv);if (arr[l].mav == arr[r].mav) {arr[x].mavsum = arr[l].mavsum + arr[r].mavsum;}else {arr[x].miv = max(arr[x].miv, min(arr[l].mav, arr[r].mav));arr[x].mavsum = arr[l].mav > arr[r].mav ? arr[l].mavsum : arr[r].mavsum;} }void down_tag(int x, int tag) {if (tag >= arr[x].mav) return;arr[x].sum -= arr[x].mavsum * (arr[x].mav - tag);arr[x].mav = tag; }void pushdown(int x) {down_tag(lson(x), arr[x].mav);down_tag(rson(x), arr[x].mav); }void build(int x, int l, int r) {if (l == r) {slld(arr[x].sum);arr[x].mav = arr[x].sum;arr[x].miv = -1;arr[x].mavsum = 1;return;}int mid = ((r - l) >>1) + l;if (l <= mid) build(lson(x), l, mid);if (r > mid) build(rson(x), mid + 1, r);pushup(x); }void modify(int x, int l, int r) {if (arr[x].mav <= qval) return;if (ql <= l && qr >= r && arr[x].miv < qval) {down_tag(x, qval);return;}pushdown(x);int mid = ((r - l) >>1) + l;if (ql <= mid) modify(lson(x), l, mid);if (qr > mid) modify(rson(x), mid + 1, r);pushup(x); }ll query_max(int x, int l, int r) {if (ql <= l && qr >= r) {return arr[x].mav;}pushdown(x);ll ans = 0;int mid = ((r - l) >>1) + l;if (ql <= mid) ans = query_max(lson(x), l, mid);if (qr > mid) ans = max(query_max(rson(x), mid + 1, r), ans);return ans; }ll query_sum(int x, int l, int r) {if (ql <= l && qr >= r) {return arr[x].sum;}ll ans = 0;pushdown(x);int mid = ((r - l) >>1) + l;if (ql <= mid) ans += query_sum(lson(x), l, mid);if (qr > mid) ans += query_sum(rson(x), mid + 1, r);return ans; }int main() {ll n, q, t;slld(t);while (t--){slld(n); slld(q);build(1, 1, n);while (q--) {ll op, l, r, val;scanf("%lld%lld%lld", &op, &ql, &qr);if (op == 0) {scanf("%lld", &qval);modify(1, 1, n);} else if (op == 1) {printf("%lld\n", query_max(1, 1, n));} else {printf("%lld\n", query_sum(1, 1, n));}}}return 0; }

?

轉(zhuǎn)載于:https://www.cnblogs.com/zfdyf/p/9126343.html

總結(jié)

以上是生活随笔為你收集整理的线段树维护最值的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。