这题开始一直被矩形框束缚了，想法一直都是枚举线，但是这样枚举都需要O（n^2）。。。但是看了别人的思路，感觉这题思想真心很好（PS：开头好浪漫的描述啊，可惜并没有什么用）
题意就是在平面上给你一些星星，一定是整数点，每颗星星有一个亮度，然后给你一个固定大小只能移动不能旋转的矩形框，问你任意移动矩形框最多可以将星星的最大的亮度装进框内，注意框边上的星星不计算
以前做过有个类似的题，但是数据范围小又很水，因为可以枚举每个点作为四个角分别统计就过了。可是这样是错的，因为可能有情况是四个点分别限制矩形框的四边，这样的情况就不能处理。
很多二维题都是二维变一维，先枚举一维，接着用一些数据结构高效的维护另一维。
这个题所使用的方法其实也是排序一维，然后模拟矩形框来维护两条扫描线在这一维上移动，接着处理第二维在限制长度内的最大值。换句话就是用两个指针维护x轴，接着用添加点，删除点的方式维护y轴。但是在限制长度下求最大区间和不太好做，我们可以模拟树状数组的区间更新，在每个点的（y轴+限制长度）的位置添加一个负的亮度，这样我们就转化为了求最大区间和（没有了限制长度），直接套一个线段树区间合并。注意这儿数据范围很大需要离散化，但是要搞清楚我们只需要离散化后的每个y值对应的是树上的哪个位置（其实就是第几大），使用map就可以解决
#include<set> #include<map> #include<queue> #include<stack> #include<cmath> #include<vector> #include<string> #include<cstdio> #include<cstring> #include<stdlib.h> #include<iostream> #include<algorithm> using namespace std; #define eps 1E-8 /*注意可能会有输出-0.000*/ #define Sgn(x) (x<-eps? -1 :x<eps? 0:1)//x为两个浮点数差的比较,注意返回整型 #define Cvs(x) (x > 0.0 ? x+eps : x-eps)//浮点数转化 #define zero(x) (((x)>0?(x):-(x))<eps)//判断是否等于0 #define mul(a,b) (a<<b) #define dir(a,b) (a>>b) typedef long long ll; typedef unsigned long long ull; const int Inf=1<<28; const double Pi=acos(-1.0); const int Max=10010; map<ll,int> mp;//离散化成1到coun struct node { ll bri; ll xx1,yy1; } poi[Max]; struct nide { ll lmax,rmax,mmax,sum; void init(ll num) { sum=lmax=rmax=mmax=num; } } segtr[Max*2<<2]; //再多开一倍空间 bool cmp1(struct node p1,struct node p2) { return p1.xx1<p2.xx1; } ll nmax(ll a,ll b) { return a>b?a:b; } void Upnow(int now,int next) { segtr[now].sum=segtr[next].sum+segtr[next|1].sum; segtr[now].lmax=nmax(segtr[next].lmax,segtr[next].sum+segtr[next|1].lmax); segtr[now].rmax=nmax(segtr[next|1].rmax,segtr[next|1].sum+segtr[next].rmax); segtr[now].mmax=nmax(nmax(segtr[next].mmax,segtr[next|1].mmax),segtr[next].rmax+segtr[next|1].lmax); return; } void Create(int sta,int enn,int now) { if(sta==enn) { segtr[now].init(0ll); return; } int mid=dir(sta+enn,1); int next=mul(now,1); Create(sta,mid,next); Create(mid+1,enn,next|1); Upnow(now,next); return; } void Update(int sta,int enn,int now,int x,ll y) { if(sta==enn&&sta==x) { segtr[now].sum+=y; segtr[now].lmax+=y; segtr[now].rmax+=y; segtr[now].mmax+=y; return; } int mid=dir(sta+enn,1); int next=mul(now,1); if(mid>=x) Update(sta,mid,next,x,y); else Update(mid+1,enn,next|1,x,y); Upnow(now,next); return; } int main() { ll n,w,h; while(~scanf("%lld %lld %lld",&n,&w,&h)) { for(int i=0; i<n; i++) scanf("%lld %lld %lld",&poi[i].xx1,&poi[i].yy1,&poi[i].bri); mp.clear(); for(int i=0; i<n; i++)//建树前离散化y轴 { mp[poi[i].yy1]=0; mp[poi[i].yy1+h]=0; } int coun=1; map<ll,int>::iterator it; for(it=mp.begin(); it!=mp.end(); ++it) it->second=coun++; coun--; Create(1,coun,1); int j=0;//双指针作为扫描线 ll manx=0; sort(poi,poi+n,cmp1); for(int i=0; i<n; i++) //关键：模拟树状数组的区间更新，后面对应位置加一个负的亮度，则就求最大区间和 { Update(1,coun,1,mp[poi[i].yy1],poi[i].bri);//加点 Update(1,coun,1,mp[poi[i].yy1+h],-poi[i].bri);//枚举的点 while(i!=j&&poi[i].xx1-poi[j].xx1>=w) { Update(1,coun,1,mp[poi[j].yy1],-poi[j].bri);//删点 Update(1,coun,1,mp[poi[j].yy1+h],poi[j].bri); j++; } manx=nmax(manx,segtr[1].mmax); } printf("%lld ",manx); } return 0; }