把點的y軸值離散化一下，假如離散完有Y個數字，那從1到Y，假設每一個數值當成矩形的下邊界，然后在開一個循環，當下邊界為1時，上邊界為1 . 2 . 3 . 4 … Y，假設下邊界為2時，上邊界為 2 . 3 . 4 … Y。以此類推，每次對于上下邊界的假設用線段樹求一次最大字段和，建樹用的值就是在上下邊界內在同一個y軸上的x的和，共有X個，離散化x軸的值可得X，然后記錄最大值。

#include <iostream> #include <stdio.h> #include <string.h> #include <stdlib.h> #include <math.h> #include <time.h> #include <algorithm> typedef long long ll; using namespace std; const ll mod=998244353; const int maxn=1e5+100;int sy[maxn],sx[maxn];struct node {ll ls,rs,s,maxs; }ans[maxn];struct point {int x,y;ll w; }wq[maxn];int cmp(point a,point b) {return a.y<b.y; }void pushup(int l,int r,int rt) {ans[rt].ls=max(ans[rt<<1].ls,ans[rt<<1].s+ans[rt<<1|1].ls);ans[rt].rs=max(ans[rt<<1|1].rs,ans[rt<<1|1].s+ans[rt<<1].rs);ans[rt].s=ans[rt<<1].s+ans[rt<<1|1].s;ans[rt].maxs=max(ans[rt<<1].rs+ans[rt<<1|1].ls,max(ans[rt<<1].maxs,ans[rt<<1|1].maxs)); }void build(int l,int r,int rt) {ans[rt].ls=ans[rt].rs=ans[rt].s=ans[rt].maxs=0;if(l==r)return;int mid=(l+r)>>1;build(l,mid,rt<<1);build(mid+1,r,rt<<1|1); }void update(int L,int R,int l,int r,int rt,int x) {if(L<=l && r<=R){ans[rt].ls=ans[rt].rs=ans[rt].s=ans[rt].maxs=ans[rt].s+x;return;}int mid=(l+r)>>1;if(L<=mid)update(L,R,l,mid,rt<<1,x);else update(L,R,mid+1,r,rt<<1|1,x);pushup(l,r,rt); }int main() { // freopen("in.txt","r",stdin); // freopen("out.txt","w",stdout);int t;scanf("%d",&t);while(t--){int n;scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%d%d%lld",&wq[i].x,&wq[i].y,&wq[i].w);sy[i]=wq[i].y;sx[i]=wq[i].x;}sort(wq+1,wq+1+n,cmp);sort(sy+1,sy+1+n);int toty=unique(sy+1,sy+1+n)-sy-1;sort(sx+1,sx+1+n);int totx=unique(sx+1,sx+1+n)-sx;int pi=1;ll maxans=0;for(int i=1;i<=toty;i++){build(1,totx,1);int pj=pi,flag=1;for(int j=i;j<=toty;j++){do{int pos=lower_bound(sx+1,sx+totx,wq[pj].x)-sx;update(pos,pos,1,totx,1,wq[pj].w);pj++;if(flag && wq[pj].y!=wq[pj-1].y && pj<=n){pi=pj,flag=0;}}while(pj<=n && wq[pj].y==wq[pj-1].y);maxans=max(maxans,ans[1].maxs);}}printf("%lld\n",maxans);}return 0; }

總結

以上是生活随笔為你收集整理的hdu 6638 2019多校训练六 1005 Snowy Smile的全部內容，希望文章能夠幫你解決所遇到的問題。

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