# 【題解】ZeroJudge e719: 108北二3.物聯網的感測器連結量問題

```#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

int n, m, bit[100005], ans;
pair <long long, long long> a[100005];
vector <int> id;

bool cmp(pair<int, int> x, pair<int, int> y){
if (x.first != y.first) return x.first < y.first;
return x.second <= y.second;
}
int lid(long long x){
return (int)(lower_bound(id.begin(), id.end(), x)-id.begin())+1;
}
int rid(long long x){
return (int)(upper_bound(id.begin(), id.end(), x)-id.begin());
}
void update(int x, int d){
while (x <= id.size()){
bit[x] += d;
x += x & (-x);
}
}
int query(int x){
int ret = 0;
while (x){
ret += bit[x];
x -= x & (-x);
}
return ret;
}

int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> m >> n;
int x, y;
for (int i = 0; i < n; i++){
cin >> x >> y;
a[i] = {x, y};
id.push_back(y);
}
sort(id.begin(), id.end());
id.erase(unique(id.begin(), id.end()), id.end());
sort(a, a+n, cmp);
queue <pair<int, int> > q;
for (int i = 0; i < n; i++){
while (!q.empty() && q.front().first < a[i].first-m){
update(lid(q.front().second), -1);
q.pop();
}
ans += query(min((int)id.size(), rid(a[i].second+m))) - query(max( 0, lid(a[i].second-m)-1));
update(lid(a[i].second), 1);
q.push(a[i]);
}
cout << ans << "\n";
}
```