題意：有n個點（n<=2000），每個點都有價值，求一個矩形內所有點價值和的最大值是多少

一維的靜態最大子段和用dp在O(n)時間內解決，帶修改查詢區間最大子段和可以用線段樹區間合并O(nlogn)寫

二維的最大子矩陣和可以通過壓行再dpO(n^3)寫。

這題對坐標離散化一下就轉化為求最大子矩陣和的問題了，然后n^3肯定是不行的，然后利用離散后是2000*2000的圖上有2000個點，矩陣很稀疏這個性質，可以通過枚舉起始行s，終點行e，用然后用線段樹維護s~e行，每列的信息，轉化為一維最大子段和來算。每次枚舉起始行時都要重新建樹，然后枚舉終點行時，都把這行的信息更新到線段樹里去，復雜度是n(nlogn(建樹)+nlogn（更新）)，這題關鍵是有效點很少只有n個，如果是n^2個就沒了。

#include<bits/stdc++.h> using namespace std; #define ls rt<<1 #define rs (rt<<1)+1 #define ll long long #define fuck(x) cout<<#x<<" "<<x<<endl; typedef pair<int,int>pii; const ll inf=9e18; const int maxn=2000+10; int d[4][2]={1,0,-1,0,0,1,0,-1}; vector<pii>row[maxn]; struct node{int x,y,w; }p[maxn]; int lshx[maxn],lshy[maxn],cnt1,cnt2; ll maxx[maxn<<2],lmaxx[maxn<<2],rmaxx[maxn<<2],sum[maxn<<2]; void pushup(int rt) {sum[rt]=sum[ls]+sum[rs];lmaxx[rt]=max(lmaxx[ls],sum[ls]+lmaxx[rs]);rmaxx[rt]=max(rmaxx[rs],sum[rs]+rmaxx[ls]);maxx[rt]=max(maxx[ls],maxx[rs]);maxx[rt]=max(maxx[rt],rmaxx[ls]+lmaxx[rs]); } void update(int rt,int L,int R,int pos,int val){if(L==R){sum[rt]+=val;maxx[rt]=lmaxx[rt]=rmaxx[rt]=max(0LL,sum[rt]);return ;}int mid=(L+R)>>1;if(pos<=mid)update(ls,L,mid,pos,val);elseupdate(rs,mid+1,R,pos,val);pushup(rt); } int main(){int t,n;ll ans;scanf("%d",&t);while(t--){ans=-inf;cnt1=cnt2=0;scanf("%d",&n);for(int i=1;i<=n;i++) row[i].clear();for(int i=1;i<=n;i++) scanf("%d%d%d",&(p[i].x),&(p[i].y),&(p[i].w)),lshx[++cnt1]=p[i].x,lshy[++cnt2]=p[i].y;sort(lshx+1,lshx+cnt1+1);sort(lshy+1,lshy+cnt2+1);cnt1=unique(lshx+1,lshx+cnt1+1)-lshx-1;cnt2=unique(lshy+1,lshy+cnt2+1)-lshy-1;for(int i=1;i<=n;i++){int tmpx,tmpy;tmpx=lower_bound(lshx+1,lshx+cnt1+1,p[i].x)-lshx;tmpy=lower_bound(lshy+1,lshy+cnt2+1,p[i].y)-lshy;row[tmpx].push_back(make_pair(tmpy,p[i].w));}for(int i=1;i<=cnt1;i++){for(int j=1;j<=cnt2*4;j++)maxx[j]=lmaxx[j]=rmaxx[j]=sum[j]=0;for(int j=i;j<=cnt1;j++){for(int k=0;k<row[j].size();k++)update(1,1,cnt2,row[j][k].first,row[j][k].second);ans=max(ans,maxx[1]);}}printf("%lld\n",ans);}return 0; }

?

總結

以上是生活随笔為你收集整理的HDU多校第六场——HDU6638 Snowy Smile（线段树区间合并）的全部內容，希望文章能夠幫你解決所遇到的問題。

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