题目描述
茶颜悦色也太好喝了！鸡尾酒在长沙的各种茶颜悦色的店铺中流连忘返。他发现长沙有炒鸡多的茶颜悦色店，走两步就能遇到一家。
“方圆一公里能有十家茶颜悦色！”鸡尾酒感叹了起来。
于是他想到了一个问题：最密集的地方，能有多少家茶颜悦色的店？
鸡尾酒将长沙地图用一个二维平面表示，他统计出了每个茶颜悦色店铺的坐标。
他想知道，在一个边长为 k 且底边平行于 x 轴的正方形中，最多有多少家茶颜悦色。
若茶颜悦色恰好在正方形的边上，也算在正方形之中。
输入描述
输入第一行包含两个正整数 n, (n≤10^5,k≤10^9) 代表茶颜悦色店的数量和正方形的边长。
接下来 n 行每行有两个整数，描述一家茶颜悦色店的坐标 xi,yi (0≤xi,yi≤10^9) 保证不会出现重复的坐标。
输出描述
输出一行一个正整数表示答案。
样例输入 1
4 2
1 1
3 1
3 4
2 2
样例输出 1
3
题意：一个二维平面中有n个点，现在有个位置任意的k*k的矩形，问它里面最多能有多少点。
题解：我们可以把这个题转化为以（xi,yi）为左下角坐标，（xi+k,yi+k）为右上角坐标的矩形中，最多能有几个个矩形重合。然后我们就可以愉快的用扫描线来处理了：我们将竖直的直线从左到右依次扫过各个矩形，扫过矩形左边界时cnt++，扫过右边界时cnt--。维护最大cnt值即可。
这题要注意的是：恰好在正方形的边上，也算在正方形之中。也就是说如果有一个矩形的右边界与另一个矩形的左边界重合的话，我们先加再减。对于这一点我们可以在存矩阵右边界时使其加一，也可以排序线段时处理。
这题与POJ2482窗内的星星相似，不过一个算边界一个不算边界，一个先加后减一个先减后加。
代码：
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 2e5 + ;
struct node{
ll x,y1,y2;
int val;
node(){}
node(ll x,ll y1,ll y2,int val) {
this->x = x; this->y1 = y1; this->y2 = y2; this->val = val;
}
bool operator <(const node &t)const {
//if (x==t.x) return val > t.val; //排序时处理
return x<t.x;
}
};
struct Tree{
int l,r,cnt,lazy;
}T[N<<];
vector<ll> v;
vector<node> a;
void build(int rt,int l,int r) {
T[rt].l = l; T[rt].r = r;
T[rt].cnt = ; T[rt].lazy = ;
if (l==r) return;
int mid = (l+r)>>;
build(rt<<,l,mid);
build(rt<<|,mid+,r);
}
void down(int rt) {
if (T[rt].lazy) {
T[rt<<].cnt += T[rt].lazy;
T[rt<<].lazy += T[rt].lazy;
T[rt<<|].cnt += T[rt].lazy;
T[rt<<|].lazy += T[rt].lazy;
T[rt].lazy = ;
}
}
void update(int rt,int l,int r,int val) {
if (l <= T[rt].l && r >= T[rt].r) {
T[rt].cnt += val;
T[rt].lazy += val;
return;
}
down(rt);
int mid = (T[rt].l+T[rt].r)>>;
if (l <= mid) update(rt<<,l,r,val);
if (r > mid) update(rt<<|,l,r,val);
T[rt].cnt = max(T[rt<<].cnt,T[rt<<|].cnt);
}
int main() {
int n;
ll k,x,y;
scanf("%d%lld",&n,&k);
for (int i = ; i < n; i++) {
scanf("%lld%lld",&x,&y);
v.push_back(y);
v.push_back(y+k);
a.push_back(node(x,y,y+k,));
a.push_back(node(x+k+,y,y+k,-)); //存的时候右边界x坐标+1
}
sort(a.begin(),a.end());
sort(v.begin(),v.end());
v.erase(unique(v.begin(),v.end()),v.end());
n = v.size();
build(,,n);
n = a.size();
int ans = ;
for (int i = ; i < n; i++) {
int l = lower_bound(v.begin(),v.end(),a[i].y1) - v.begin();
int r = lower_bound(v.begin(),v.end(),a[i].y2) - v.begin();
update(,l,r,a[i].val);
ans = max(ans,T[].cnt);
}
printf("%d\n",ans);
return ;
}