题干：
Recently, the γ galaxies broke out Star Wars. Each planet is warring for resources. In the Star Wars, Planet X is under attack by other planets. Now, a large wave of enemy spaceships is approaching. There is a very large Beam Cannon on the Planet X, and it is very powerful, which can destroy all the spaceships in its attack range in a second. However, it takes a long time to fill the energy of the Beam Cannon after each shot. So, you should make sure each shot can destroy the enemy spaceships as many as possible.
To simplify the problem, the Beam Cannon can shot at any area in the space, and the attack area is rectangular. The rectangle parallels to the coordinate axes and cannot rotate. It can only move horizontally or vertically. The enemy spaceship in the space can be considered as a point projected to the attack plane. If the point is in the rectangular attack area of the Beam Cannon(including border), the spaceship will be destroyed.
Input
Input contains multiple test cases. Each test case contains three integers N(1<=N<=10000, the number of enemy spaceships), W(1<=W<=40000, the width of the Beam Cannon’s attack area), H(1<=H<=40000, the height of the Beam Cannon’s attack area) in the first line, and then N lines follow. Each line contains two integers x,y (-20000<=x,y<=20000, the coordinates of an enemy spaceship).
A test case starting with a negative integer terminates the input and this test case should not to be processed.
Output
Output the maximum number of enemy spaceships the Beam Cannon can destroy in a single shot for each case.
Sample Input
2 3 4
0 1
1 0
3 1 1
-1 0
0 1
1 0
-1 Sample Output
2
2 题目大意：
给你一个矩形的宽度和长度，然后给你一些点的坐标，让你输出这个矩形最多能覆盖多少个点。
解题报告：
类似扫描线的思想，将一条边拆成两条边，权值分别为1和-1。
AC代码1：（其实这里的.f，用laz比较合适）
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<queue>
#include<map>
#include<vector>
#include<set>
#include<string>
#include<cmath>
#include<cstring>
#define ll long long
#define pb push_back
#define pm make_pair
using namespace std;
const int MAX = 2e5 + 5;
struct Node {
int x,y;
int f;
bool operator < (const Node &a)const{
if(y==a.y) return f<a.f;
return y<a.y;
}
} node[MAX];
struct TREE {
int l,r;
int f,val;
} tree[400005 * 16];//???????????????????
void pushdown(int cur) {
if(tree[cur].f == 0) return;
int tmp = tree[cur].f;
tree[cur].f = 0;
tree[cur*2].f += tmp;
tree[cur*2+1].f += tmp;
tree[cur*2].val += tmp;
tree[cur*2+1].val += tmp;
}
void build(int l,int r,int cur) {
tree[cur].l=l,tree[cur].r=r;
tree[cur].f = tree[cur].val = 0;
if(l == r) return;
int m = (l+r)>>1;
build(l,m,cur*2);
build(m+1,r,cur*2+1);
}
void update(int pl,int pr,int val,int cur) {
if(pl <= tree[cur].l && pr >= tree[cur].r) {
//pushup(cur);
tree[cur].f += val;
tree[cur].val += val;
return ;
}
pushdown(cur);
if(tree[cur*2].r >= pl) update(pl,pr,val,cur*2);
if(tree[cur*2+1].l <= pr) update(pl,pr,val,cur*2+1);
//pushup(cur);
tree[cur].val = max(tree[cur*2].val,tree[cur*2+1].val);
}
int main()
{
int n,W,H;
while(cin>>n) {
if(n == -1) break;
cin>>W>>H;
for(int a,b,i = 1; i<=2*n; i+=2) {
scanf("%d%d",&a,&b);a+=20005;
node[i].x=a;node[i+1].x=a;
node[i].y=b;node[i+1].y=b+H+1;
node[i].f=1;node[i+1].f=-1;
}
sort(node+1,node+2*n+1);
build(1,10005*8,1);
int ans = 0;
for(int i = 1; i<=2*n; i++) {
update(node[i].x,node[i].x + W,node[i].f,1);
ans = max(ans,tree[1].val);
}
printf("%d\n",ans);
}
return 0 ;
} AC代码3：
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<queue>
#include<map>
#include<vector>
#include<set>
#include<string>
#include<cmath>
#include<cstring>
#define ll long long
#define pb push_back
#define pm make_pair
using namespace std;
const int MAX = 2e5 + 5;
struct Node {
int x,y;
int f;
bool operator < (const Node &a)const{
return x<a.x;
}
} node[MAX];
struct TREE {
int l,r;
int f,val;
} tree[400005 * 16];//???????????????????
void pushdown(int cur) {
if(tree[cur].f == 0) return;
int tmp = tree[cur].f;
tree[cur].f = 0;
tree[cur*2].f += tmp;
tree[cur*2+1].f += tmp;
tree[cur*2].val += tmp;
tree[cur*2+1].val += tmp;
}
void build(int l,int r,int cur) {
tree[cur].l=l,tree[cur].r=r;
tree[cur].f = tree[cur].val = 0;
if(l == r) return;
int m = (l+r)>>1;
build(l,m,cur*2);
build(m+1,r,cur*2+1);
}
void update(int pl,int pr,int val,int cur) {
if(pl <= tree[cur].l && pr >= tree[cur].r) {
//pushup(cur);
tree[cur].f += val;
tree[cur].val += val;
return ;
}
pushdown(cur);
if(tree[cur*2].r >= pl) update(pl,pr,val,cur*2);
if(tree[cur*2+1].l <= pr) update(pl,pr,val,cur*2+1);
//pushup(cur);
tree[cur].val = max(tree[cur*2].val,tree[cur*2+1].val);
}
int main()
{
int n,W,H;
while(cin>>n) {
if(n == -1) break;
cin>>W>>H;
for(int a,b,i = 1; i<=2*n; i+=2) {
scanf("%d%d",&a,&b);b+=20000;
node[i].x=a;node[i+1].x=a+W+1;
node[i].y=b;node[i+1].y=b;
node[i].f=1;node[i+1].f=-1;
}
sort(node+1,node+2*n+1);
build(0,10005*8,1);
int ans = 0;
for(int i = 1; i<=2*n; i++) {
update(node[i].y,node[i].y + H,node[i].f,1);
ans = max(ans,tree[1].val);
}
printf("%d\n",ans);
}
return 0 ;
} AC代码4：（其实排序来说最标准的应该是这样）
struct Node {
int x,y;
int f;
bool operator < (const Node &a)const{
if(x==a.x) return f<a.f;
return x<a.x;
}
} node[MAX];
京公网安备 11010502036488号