【題解】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";
}