題目鏈接、

題意：

給你n個點（小于等于2e3個），每個點有個價值val，有個x，y坐標（這三個值都是1e9的）

讓你求一個最大的子矩陣和

T組（100）

題解：

線段樹維護子段和

因為x，y，太大，所以要離散化，之后是一個n*n的矩陣，

這時，原本有一個算法，即，枚舉一個上下界，然后一個的dp

當時我就這么寫的，想了半天不造咋優(yōu)化

后來才知道，線段樹可以維護子段和

?

其實知道思想之后，很簡單。。

線段樹的精髓——區(qū)間合并，考慮怎么合并就行了：

1、合并的答案要么左區(qū)間的子段和，要么是右區(qū)間的子段和，要么是中間的一部分

2、考慮中間這部分怎么求，也就是說，其實求一個區(qū)間的最大，前后綴就行了，因為中間這部分就是

左區(qū)間的最大后綴+右區(qū)間的最大前綴

3、考慮怎么維護區(qū)間的前后綴、前綴的話，肯定是左區(qū)間前綴 ??和 ?左區(qū)間的區(qū)間和加右區(qū)間的前綴 ?取一個最大值

后綴同理

?

注意到這里，只需要查詢的是整個區(qū)間所有，連詢問函數(shù)也不用寫了，直接找根節(jié)點的值就行了

?

/*author:revolIA*/ #include<bits/stdc++.h> using namespace std; typedef long long ll; const int maxn = 1e4+7; int T,n; struct node{ll lsum,rsum,sum,Ans;void update(ll x){lsum += x;rsum += x;sum += x;Ans += x;} }tree[maxn<<2]; void push_up(int x){tree[x].sum = tree[x<<1].sum+tree[x<<1|1].sum;tree[x].lsum = max(tree[x<<1].lsum,tree[x<<1].sum+tree[x<<1|1].lsum);tree[x].rsum = max(tree[x<<1|1].rsum,tree[x<<1|1].sum+tree[x<<1].rsum);tree[x].Ans = max(max(tree[x<<1].Ans,tree[x<<1|1].Ans),tree[x<<1].rsum+tree[x<<1|1].lsum); } void build(int L = 1,int R = n,int x = 1){tree[x].lsum = tree[x].rsum = 0;tree[x].sum = tree[x].Ans = 0;if(L == R)return;int mid = L+R>>1;build(L,mid,x<<1),build(mid+1,R,x<<1|1);//push_up(x); } void update(int k,ll val,int L=1,int R=n,int x = 1){if(L == R){tree[x].update(val);}else{int mid = L+R>>1;if(k<=mid)update(k,val,L,mid,x<<1);else update(k,val,mid+1,R,x<<1|1);push_up(x);} } vector<int> vecL,vecU; vector<pair<int,ll> > vec[maxn]; ll x[maxn],y[maxn],val[maxn]; int main(){for(scanf("%d",&T);T--;){scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%lld%lld%lld",&x[i],&y[i],&val[i]);vecL.push_back(x[i]);vecU.push_back(y[i]);}sort(vecL.begin(),vecL.end());vecL.erase(unique(vecL.begin(),vecL.end()),vecL.end());sort(vecU.begin(),vecU.end());vecU.erase(unique(vecU.begin(),vecU.end()),vecU.end());for(int i=1;i<=n;i++){int x_ = lower_bound(vecL.begin(),vecL.end(),x[i])-vecL.begin()+1;int y_ = lower_bound(vecU.begin(),vecU.end(),y[i])-vecU.begin()+1;vec[x_].push_back(make_pair(y_,val[i]));}ll ans = 0;for(int i=1;i<=n;i++){build();for(int j=i;j<=n;j++){for(auto k:vec[j])update(k.first,k.second);ans = max(ans,tree[1].Ans);}}printf("%lld\n",ans);vecL.clear();vecU.clear();for(int i=1;i<=n;i++)vec[i].clear();}return 0; }

?

總結

以上是生活随笔為你收集整理的2019杭电多校6，E.Snowy Smile（线段树维护子段和）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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