Với bài này, chúng ta có thể cố định $x$ rồi xử lý $y$ hoặc ngược lại. Giả sử, đang xét ở vị trí $i$,
ta có $ 1 \le i \le max_x$ thì lúc này ta chỉ xét với các cặp $(x, y)$ sao cho $x$ nằm trong đoạn $[i, i + k]$. Ở phần xử lí toạ độ $y$, bởi vì chỉ xét trong đoạn có độ dài $= k$
nên với mỗi $y$, ta $update$ đoạn $[y, y + k]$ hoặc là $[y - k, y]$ thêm lên 1. ($-$ hay $+$ thì có thể phụ thuộc vào bạn đọc).
Lúc đó hình vuông có độ dài $k$ chính là $max$ của $[1, y]$. Với cách đó, chúng ta dùng một SegmentTree Lazy để xử lí.
Chứng minh
https://drive.google.com/file/d/1jfT95br7ZOC1nQ1G1NhzoczMMxwojV80/view?usp=sharing
Đây là code mẫu của mình:
```cpp
/* /\_/\
( ._. ) ~UwU~
/ >0< \
/*Author TViu*/
#include<bits/stdc++.h>
#define _Vixingggg_ signed main()
using namespace std;
#define Vi ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define int long long
#define el '\n'
#define pb push_back
#define all(x) x.begin(), x.end()
#define fi first
#define se second
#define pii pair<int,int>
#define vi vector<int>
#define FOU(i, a, b) for(int i = (a), _b = (b); i <= _b; ++i)
#define FOD(i, a, b) for(int i = (a), _b = (b); i >= _b; --i)
#define REP(i, n) for(int i = 0, _n = (n); i < _n ;++i)
#define TASK "task"
#define TIME cerr << "\nTime: " << 1000.0 * clock() / CLOCKS_PER_SEC << " ms.";
#define Nho if(fopen(TASK".inp","r")){freopen(TASK".inp","r",stdin);freopen(TASK".out","w",stdout);}
template<typename T> void maxi(T& res,const T &val){res = res < val ? val : res;};
template<typename T> void mini(T& res,const T &val){res = res > val ? val : res;};
template<typename T> void dvxt(T& res,const T &mod){res >= mod ? res -= mod : (res < 0 ? res += mod : res += 0);};
//----------------------------CONSTANTS-----------------------------------
const int mod = 1e9+7;
const int oo = 1e18;
const int N = 1e6+7;
const int lim = 1 << 17;
//---------------------------STRUCT---------------------------------------
struct LazySeg{
int st[lim << 1], lazy[lim << 1];
void push(int id, int l, int r){
if (!lazy[id]) return;
st[id] += lazy[id];
if (l != r){
lazy[id << 1] += lazy[id];
lazy[id << 1 | 1] += lazy[id];
}
lazy[id] = 0;
}
void update(int u, int v, int val = 1, int id = 1, int l = 1, int r = lim){
push(id, l, r);
if (v < l || u > r) return;
if (u <= l && r <= v){
lazy[id] += val;
push(id, l, r);
return;
}
int mid = l + r >> 1;
update(u, v, val, id << 1, l, mid);
update(u, v, val, id << 1 | 1, mid + 1, r);
st[id] = max(st[id << 1], st[id << 1 | 1]);
}
int query(){
push(1, 1, lim);
return st[1];
}
} Seg;
//---------------------------VARIABLE-------------------------------------
int n, k, a[N];
vi pos[N];
//---------------------------FUNCTION-------------------------------------
void solve(){
cin >> n >> k;
FOU(i, 1, n){
int x, y; cin >> x >> y;
pos[x].pb(y);
}
int res = 0;
FOD(i, lim, 1){
for (int j : pos[i + k + 1]) Seg.update(j, j + k, -1);
for (int j : pos[i]) Seg.update(j, j + k, 1);
maxi(res, Seg.query());
}
cout << res << el;
}
//---------------------------MAIN PRO-------------------------------------
_Vixingggg_{
Vi Nho
int tt=1;
//cin >> tt;
for (int i = 1; i <= tt; ++i){
solve();
}
TIME
return 0^0;
}
```
TViu
Created at
0 likes