?

題意：在二維平面上有一些點 每個點有權值 ? 問怎樣選定一個矩形 ?取這個矩形內(nèi)部的所有權值 ?使得權值和最大

?

比賽的時候沒想出來可惜了 ?

一直在想枚舉上下邊界 ?但枚舉上下邊界已經(jīng)用了n2了 ? 剩下一個log肯定不夠

?

可以只枚舉上邊界 ?然后動態(tài)枚舉下邊界 ?

?

注意更新的時候一定要等到 ? a[j].x!=a[j-1].x

#include<bits/stdc++.h> using namespace std; //input by bxd #define rep(i,a,b) for(int i=(a);i<=(b);i++) #define repp(i,a,b) for(int i=(a);i>=(b);--i) #define ll long long #define see(x) (cerr<<(#x)<<'='<<(x)<<endl) #define pb push_back #define inf 0x3f3f3f3f #define CLR(A,v) memset(A,v,sizeof A) typedef pair<int,int>pii; // const int N=2e6+10;#define lson l,m,pos<<1 #define rson m+1,r,pos<<1|1ll lmax[N<<2],rmax[N<<2],t[N<<2],maxans[N<<2];void up(int pos) {t[pos]=t[pos<<1]+t[pos<<1|1];maxans[pos]=max( max(maxans[pos<<1],maxans[pos<<1|1]),rmax[pos<<1]+lmax[pos<<1|1] );lmax[pos]=max(lmax[pos<<1],t[pos<<1]+lmax[pos<<1|1]);rmax[pos]=max(rmax[pos<<1|1],t[pos<<1|1]+rmax[pos<<1]); } void build(int l,int r,int pos) {if(l==r){lmax[pos]=rmax[pos]=t[pos]=maxans[pos]=0;return ; }int m=(l+r)>>1;build(lson);build(rson);up(pos); } void upnode(int x,ll v,int l,int r,int pos) {if(l==r){t[pos]+=v; lmax[pos]=rmax[pos]=maxans[pos]=max(1ll*0,t[pos]);return ;}int m=(l+r)>>1;if(x<=m)upnode(x,v,lson);else upnode(x,v,rson);up(pos); } int n,k,b[N],nn;struct node {int x,y,w; }a[N]; int main() {int cas;cin>>cas;while(cas--){scanf("%d",&n);rep(i,1,n){scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].w);b[++nn]=a[i].y;}sort(b+1,b+1+nn);nn=unique(b+1,b+1+nn)-b-1;rep(i,1,n)a[i].y=lower_bound(b+1,b+1+nn,a[i].y)-b;sort(a+1,a+1+n,[](node a,node b){return a.x<b.x||a.x==b.x&&a.y<b.y;});ll ans=0;rep(i,1,n){if(i!=1&&a[i].x==a[i-1].x)continue;build(1,nn,1);rep(j,i,n){if(j!=i&&a[j].x!=a[j-1].x)ans=max(ans,maxans[1]);upnode(a[j].y,1ll*a[j].w,1,nn,1);}ans=max(ans,maxans[1]);}cout<<ans<<endl;}return 0; } View Code

?

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

總結

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

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