UVA - 11992

題意：有一個 r*c 的全 0矩陣, 進行 3 種操作。
1 x1 y1 x2 y2 val 表示將(x1,y1,x2,y2)（x1<=x2,y1<=y2）子矩陣中的所有元素加val；
2 x1 y1 x2 y2 val 表示將(x1,y1,x2,y2)（x1<=x2,y1<=y2）子矩陣中的所有元素變為val；
3 x1 y1 x2 y2 val 表示輸出(x1,y1,x2,y2)（x1<=x2,y1<=y2）子矩陣中的所有元素的和，最小值和最大值。
共有m次操作(1<=m<=20000) 。? 矩陣不超過20 行，元素總數不超過 1e6 。

tags：因為不超過 20行，所以我們每行建棵線段樹，然后就是基本的區間更新查詢。

#include<bits/stdc++.h> using namespace std; #pragma comment(linker, "/STACK:102400000,102400000") #define rep(i,a,b) for (int i=a; i<=b; ++i) #define per(i,b,a) for (int i=b; i>=a; --i) #define mes(a,b) memset(a,b,sizeof(a)) #define INF 0x3f3f3f3f #define MP make_pair #define PB push_back #define fi first #define se second #define mid (l+(r-l)/2) #define PIII pair<ll, pair< ll, ll > > typedef long long ll; const int N = 1000005;struct Item {ll sum, minn, maxn, addv, setv; } ; vector< Item > tr[21]; int n, m, q; void Init() {rep(i,1,n) tr[i].clear();rep(i,1,n) rep(j,1,m<<2)tr[i].PB(Item()); } void pushdown(int ii, int ro, int l, int r) {if(tr[ii][ro].setv) {tr[ii][ro<<1].addv = tr[ii][ro<<1|1].addv = 0;tr[ii][ro<<1].setv = tr[ii][ro<<1|1].setv = tr[ii][ro].setv;tr[ii][ro<<1].sum = tr[ii][ro].setv*(mid-l+1);tr[ii][ro<<1|1].sum = tr[ii][ro].setv*(r-mid);tr[ii][ro<<1].maxn = tr[ii][ro<<1].minn = tr[ii][ro].setv;tr[ii][ro<<1|1].maxn = tr[ii][ro<<1|1].minn = tr[ii][ro].setv;}tr[ii][ro<<1].addv += tr[ii][ro].addv;tr[ii][ro<<1|1].addv += tr[ii][ro].addv;tr[ii][ro<<1].sum += tr[ii][ro].addv*(mid-l+1);tr[ii][ro<<1|1].sum += tr[ii][ro].addv*(r-mid);tr[ii][ro<<1].maxn += tr[ii][ro].addv;tr[ii][ro<<1].minn += tr[ii][ro].addv;tr[ii][ro<<1|1].maxn += tr[ii][ro].addv;tr[ii][ro<<1|1].minn += tr[ii][ro].addv;tr[ii][ro].addv = tr[ii][ro].setv = 0; } void pushup(int ii, int ro) {tr[ii][ro].maxn = max(tr[ii][ro<<1].maxn, tr[ii][ro<<1|1].maxn);tr[ii][ro].minn = min(tr[ii][ro<<1].minn, tr[ii][ro<<1|1].minn);tr[ii][ro].sum = tr[ii][ro<<1].sum + tr[ii][ro<<1|1].sum; } void update(int ii, int ro, int l, int r, int ql, int qr, int flag, int vi) {if(ql<=l && r<=qr) {if(flag==1) {tr[ii][ro].addv += vi;tr[ii][ro].sum += 1LL*vi*(r-l+1);tr[ii][ro].maxn += vi;tr[ii][ro].minn += vi;} else {tr[ii][ro].setv = vi;tr[ii][ro].addv = 0;tr[ii][ro].sum = 1LL*vi*(r-l+1);tr[ii][ro].maxn = tr[ii][ro].minn = vi;}return ;}pushdown(ii, ro, l, r);if(mid<qr) update(ii, ro<<1|1, mid+1, r, ql, qr, flag, vi);if(ql<=mid) update(ii, ro<<1, l, mid, ql, qr, flag, vi);pushup(ii, ro); } PIII get_ans(PIII x, PIII y) {PIII ret;ret.fi = x.fi+y.fi;ret.se.fi = max(x.se.fi, y.se.fi);ret.se.se = min(x.se.se, y.se.se);return ret; } PIII query(int ii, int ro, int l, int r, int ql, int qr) {if(ql<=l && r<=qr) {return MP(tr[ii][ro].sum, MP(tr[ii][ro].maxn, tr[ii][ro].minn));}pushdown(ii, ro, l, r);PIII ret = MP(0, MP(0,1e18));if(mid<qr) ret = get_ans(ret, query(ii, ro<<1|1, mid+1, r, ql, qr));if(ql<=mid) ret = get_ans(ret, query(ii, ro<<1, l, mid, ql, qr));pushup(ii, ro);return ret; } int main() {while(~scanf("%d%d%d", &n, &m, &q)){Init();int ti, x1, y1, x2, y2, vi;while(q--){scanf("%d", &ti);if(ti==1) {scanf("%d%d%d%d%d", &x1, &y1, &x2, &y2, &vi);rep(i,x1,x2) update(i, 1, 1, m, y1, y2, 1, vi);}else if(ti==2) {scanf("%d%d%d%d%d", &x1, &y1, &x2, &y2, &vi);rep(i,x1,x2) update(i, 1, 1, m, y1, y2, 2, vi);}else {scanf("%d%d%d%d", &x1, &y1, &x2, &y2);PIII ans = MP(0, MP(0,1e18));rep(i,x1,x2) ans = get_ans(ans, query(i, 1, 1, m, y1, y2));printf("%lld %lld %lld\n", ans.fi, ans.se.se, ans.se.fi);}}}return 0; }

轉載于:https://www.cnblogs.com/sbfhy/p/8453900.html

總結

以上是生活随笔為你收集整理的UVA - 11992 线段树的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。