POJ 2482 Stars in Your Window（掃描線）

題意：給你10000以内的星星的坐标和星星的亮度（即分别為x,y,c），要求用W*H的矩形去圍住一個區域，使得這個區域内的星星的亮度最大，并且要求矩形邊框上的星星不計入内。矩形可以平移，但不能旋轉。

對于每一個星星，分别建立線(x,y,y+H,c)和(x+W,y,y+H,-c)。這樣處理的原因是我們就可以把問題轉化成求線段樹裡某一段内的最大值，即區間查詢。矩形邊框上的星星不計的處理方法是：1.對于x軸方面的處理是在排序的時候，優先-c的邊，因為如果優先+c的邊，那麼就是将邊框上的星星計入了。2.對于y軸方面的，我的處理方法是将線段樹的葉子結點處理成長度為1的區間即[0，1]，[1，2]。。。這樣，那麼在處理比如覆寫範圍是在（0，1），（1，2）的邊時，就能避免邊框的問題，即點2不會被兩個邊更新到，因為更新的是長度為1的區間。要用離散化。

/*代碼風格更新後*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;

#define LL(x) (x<<1)
#define RR(x) (x<<1|1)
#define MID(a,b) (a+((b-a)>>1))
const int N=20005;
typedef long long LL;

struct Line
{
	LL x,y1,y2,valu;
	Line(){}
	Line(LL a,LL b,LL c,LL d)
	{ x=a;y1=b;y2=c;valu=d; }
	bool operator<(const Line&b)const
	{
		return x<b.x||(x==b.x&&valu<b.valu);
	}
};
struct node
{
	int lft,rht;
	int flag,mx;
	int mid(){return MID(lft,rht);}
	void fun(int valu)
	{
		mx+=valu;flag+=valu;
	}
};

vector<LL> y;
vector<Line> line;
map<LL,int> H;

struct Segtree
{
	node tree[N*4];
	void build(int lft,int rht,int ind)
	{
		tree[ind].lft=lft;	tree[ind].rht=rht;
		tree[ind].mx=0;		tree[ind].flag=0;
		if(lft+1!=rht)
		{
			int mid=tree[ind].mid();
			build(lft,mid,LL(ind));
			build(mid,rht,RR(ind));
		}
	}
	void updata(int st,int ed,int ind,int valu)
	{
		int lft=tree[ind].lft,rht=tree[ind].rht;
		if(st<=lft&&rht<=ed) tree[ind].fun(valu);
		else 
		{
			if(tree[ind].flag)
			{
				tree[LL(ind)].fun(tree[ind].flag);
				tree[RR(ind)].fun(tree[ind].flag);
				tree[ind].flag=0;
			}
			int mid=tree[ind].mid();
			if(st<mid) updata(st,ed,LL(ind),valu);
			if(ed>mid) updata(st,ed,RR(ind),valu);
			tree[ind].mx=max(tree[LL(ind)].mx,tree[RR(ind)].mx);
		}
	}
}seg;
int main()
{
	int n,w,h;
	while(scanf("%d%d%d",&n,&w,&h)!=EOF)
	{
		y.clear(); H.clear(); line.clear();

		for(int i=0;i<n;i++)
		{
			LL a,b,c;
			scanf("%lld%lld%lld",&a,&b,&c);
			line.push_back(Line(a,b,b+h,c));
			line.push_back(Line(a+w,b,b+h,-c));
			y.push_back(b); y.push_back(b+h); 
		}
		sort(line.begin(),line.end());
		sort(y.begin(),y.end());
		y.erase(unique(y.begin(),y.end()),y.end());
		
		for(int i=0;i<(int)y.size();i++) H[y[i]]=i;

		int mx=0;
		seg.build(0,(int)y.size()-1,1);
		for(int i=0;i<(int)line.size();i++)
		{
			seg.updata(H[line[i].y1],H[line[i].y2],1,line[i].valu);
			mx=max(mx,seg.tree[1].mx);
		}
		printf("%d\n",mx);
	}
	return 0;
}
           

#include <iostream>
/*代碼風格更新前*/
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N=20005;
LL order[N];
struct Line
{
    LL x,y1,y2;
    int valu;
    Line(){}
    Line(LL a,LL b,LL c,int d){x=a;y1=b;y2=c;valu=d;}
    bool operator < (const Line &b) const {
        return x<b.x||(x==b.x&&valu<b.valu);
    }
}line[N];
struct node
{
	int left,right;
	int iadd,imax;
	int mid(){return left+(right-left)/2;}
	void change(int valu){iadd+=valu;imax+=valu;}
};
struct Segtree
{
	node tree[N*4];
	void clear(){memset(tree,0,sizeof(tree));}
	void build(int left,int right,int ind)
	{
		tree[ind].left=left;	tree[ind].right=right;
		tree[ind].iadd=0;		tree[ind].imax=0;
		if(left+1!=right)
		{
			int mid=tree[ind].mid();
			build(left,mid,ind*2);
			build(mid,right,ind*2+1);
		}
	}
	void updata(int be,int end,int ind,int valu)
	{
		int left=tree[ind].left,right=tree[ind].right;
		if(be<=left&&right<=end) tree[ind].change(valu);
		else 
		{
			if(tree[ind].iadd)//懶操作，相當于push_down
			{
				tree[ind*2].change(tree[ind].iadd);
				tree[ind*2+1].change(tree[ind].iadd);
				tree[ind].iadd=0;
			}
			int mid=tree[ind].mid();
			if(be<mid) updata(be,end,ind*2,valu);
			if(end>mid) updata(be,end,ind*2+1,valu);
			tree[ind].imax=max(tree[ind*2].imax,tree[ind*2+1].imax);
		}
	}
}seg;
int main()
{
	int n,w,h;
	while(scanf("%d%d%d",&n,&w,&h)!=EOF)
	{
		int res=0;
		seg.clear();

		for(int i=0;i<n;i++)
		{
			int x,y,valu;
			scanf("%d%d%d",&x,&y,&valu);
			order[i*2]=y;	order[i*2+1]=(LL)y+h;
			line[i*2]=Line(x,y,(LL)y+h,valu);
			line[i*2+1]=Line((LL)x+w,y,(LL)y+h,-valu);
		}

		sort(line,line+n*2);
		sort(order,order+n*2);
		int cnt=unique(order,order+n*2)-order;
		seg.build(0,cnt,1);
		for(int i=0;i<n*2;i++)
		{
			int y1=lower_bound(order,order+cnt,line[i].y1)-order;
			int y2=lower_bound(order,order+cnt,line[i].y2)-order;
			seg.updata(y1,y2,1,line[i].valu);
			res=max(res,seg.tree[1].imax);
		}
		printf("%d\n",res);
	}
	return 0;
}