題目鏈接：http://acm.hdu.edu.cn/showproblem.php?pid=6638
題目大意：在二維平面空間有 n 個(gè)點(diǎn)，每個(gè)點(diǎn)有一個(gè)點(diǎn)權(quán) wi，一個(gè)邊平行于坐標(biāo)軸的矩形的權(quán)值為該矩形內(nèi)所有點(diǎn)的點(diǎn)權(quán)和。問選取一個(gè)矩形點(diǎn)權(quán)和最大是多少。

題解：先將坐標(biāo)離散化，以x坐標(biāo)建線段樹，枚舉y坐標(biāo)上界和下界，將y坐標(biāo)位于上下界內(nèi)的點(diǎn)加入線段樹，每次查詢線段樹最大子段和。

#include<bits/stdc++.h> using namespace std; const int maxn = 1e4 + 10; typedef long long ll; struct ss{int l,r;ll lv,rv,mv,sum; }tree[maxn << 2]; void pushup(int rt){tree[rt].lv = max(tree[rt << 1].lv,tree[rt << 1].sum + tree[rt << 1 | 1].lv);tree[rt].rv = max(tree[rt << 1 | 1].rv,tree[rt << 1 | 1].sum + tree[rt << 1].rv);tree[rt].mv = max(max(tree[rt << 1].mv,tree[rt << 1 | 1].mv),tree[rt << 1].rv + tree[rt << 1 | 1].lv);tree[rt].sum = tree[rt << 1].sum + tree[rt << 1 | 1].sum; } void build(int rt,int l,int r){tree[rt].l = l;tree[rt].r = r;if(tree[rt].l == tree[rt].r){tree[rt].lv = tree[rt].rv = tree[rt].mv = tree[rt].sum = 0;return ;}int mid = l + r >> 1;build(rt << 1,l,mid);build(rt << 1 | 1,mid + 1,r);pushup(rt); } void update(int rt,int p,ll k){if(tree[rt].l == tree[rt].r){tree[rt].lv += k;tree[rt].rv += k;tree[rt].mv += k;tree[rt].sum += k;return ;}int mid = tree[rt].l + tree[rt].r >> 1;if(p > mid) update(rt << 1 | 1,p,k);else update(rt << 1,p,k);pushup(rt); } ss query(int rt,int l,int r){if(tree[rt].l >= l && tree[rt].r <= r) return tree[rt];int mid = tree[rt].l + tree[rt].r >> 1;if(l <= mid && r > mid){ //如果跨了兩個(gè)區(qū)間 ss x1 = query(rt << 1,l,mid);ss x2 = query(rt << 1 | 1,mid + 1,r);ss ans;ans.lv = max(x1.lv,x1.sum + x2.lv);ans.rv = max(x2.rv,x2.sum + x1.rv);ans.mv = max(max(x1.mv,x2.mv),x1.rv + x2.lv);ans.sum = x1.sum + x2.sum;return ans;}else{if(l > mid) return query(rt << 1 | 1,l,r);else return query(rt << 1,l,r);} } int t,n; int x[maxn],y[maxn],z[maxn]; int tx[maxn],ty[maxn],px,py; vector<int> g[maxn]; int main() {scanf("%d",&t);while(t--) {px = py = 0;scanf("%d",&n);for(int i = 1; i <= n; i++) {scanf("%d%d%d",&x[i],&y[i],&z[i]);tx[i] = x[i];ty[i] = y[i];g[i].clear();}sort(tx + 1,tx + n + 1,less<int>());sort(ty + 1,ty + n + 1,less<int>());px = unique(tx + 1,tx + n + 1) - tx - 1;py = unique(ty + 1,ty + n + 1) - ty - 1;for(int i = 1; i <= n; i++) {x[i] = lower_bound(tx + 1,tx + px + 1,x[i]) - tx;y[i] = lower_bound(ty + 1,ty + py + 1,y[i]) - ty;}for(int i = 1; i <= n; i++)g[y[i]].push_back(i);ll ans = 0;for(int i = 1; i <= py; i++) {build(1,1,px);for(int j = i; j <= py; j++) {for(auto k : g[j])update(1,x[k],z[k]);ss res = query(1,1,px);ans = max(ans,res.mv);}}printf("%lld\n",ans);}return 0; }

總結(jié)

以上是生活随笔為你收集整理的2019 Multi-University Training Contest 6：Snowy Smile（线段树查询最大子段和）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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