题解：AT_abc366_e [ABC366E] Manhattan Multifocal Ellipse

· · 题解

提供一个非常直观，不用脑子，只需要代码能力的做法。

不难发现 x,y 的和其实独立，所以先给 x,y 排序，然后考虑枚举 x，然后求出对应的 y 的数量。

根据仓库选址那题，我们可以得到 \displaystyle\sum_{i=1}^n|y-y_i| 其实是以 y_{\left\lceil \frac{n}{2}\right\rceil} 为峰的单峰函数，所以我们可以二分处理。

代码中用双指针优化了当前不大于 x,y 的 x_i,y_i 的最大 i。

#include <iostream>
#include <iomanip>
#include <cstdio>
#include <vector>
#include <stack>
#include <queue>
#include <bitset>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <cstring>
#include <sstream>
#include <algorithm>
#include <cmath>
#include <ctime>
#include <cassert>
#include <chrono>
#include <random>
#define x first
#define y second
#define pb push_back
#define eb emplace_back
#define pf push_front
#define desktop "C:\\Users\\incra\\Desktop\\"
#define IOS ios :: sync_with_stdio (false),cin.tie (0),cout.tie (0)
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair <int,int> PII;
const int dx[] = {1,0,-1,0},dy[] = {0,-1,0,1};
template <typename T1,typename T2> bool tomax (T1 &x,T2 y) {
    if (y > x) return x = y,true;
    return false;
}
template <typename T1,typename T2> bool tomin (T1 &x,T2 y) {
    if (y < x) return x = y,true;
    return false;
}
LL power (LL a,LL b,LL p) {
    LL ans = 1;
    while (b) {
        if (b & 1) ans = ans * a % p;
        a = a * a % p;
        b >>= 1;
    }
    return ans;
}
int fastio = (IOS,0);
#define puts(s) cout << s << endl
#define endl '\n'
const int N = 2000010;
int n,d;
LL x[N],y[N];
LL slx[N],srx[N],sly[N],sry[N];
int posx;
int mp[2 * N];
LL get (LL a,LL posx,LL sl[N],LL sr[N]) {
    return posx * a - sl[posx] + sr[posx + 1] - (n - posx) * a;
}
bool check (LL a,LL b) {
    int posy = mp[b + N];
//  cout << a << ' ' << b << ' ' << get (a,posx,slx,srx) + get (b,posy,sly,sry) << endl;
    return get (a,posx,slx,srx) + get (b,posy,sly,sry) <= d;
}
int main () {
    cin >> n >> d;
    for (int i = 1;i <= n;i++) cin >> x[i] >> y[i];
    sort (x + 1,x + n + 1),sort (y + 1,y + n + 1);
    int j = 0;
    for (int i = -2e6;i <= 2e6;i++) {
        while (j + 1 <= n && y[j + 1] <= i) j++;
        mp[i + N] = j;
    }
    for (int i = 1;i <= n;i++) slx[i] = slx[i - 1] + x[i],sly[i] = sly[i - 1] + y[i];
    for (int i = n;i >= 1;i--) srx[i] = srx[i + 1] + x[i],sry[i] = sry[i + 1] + y[i];
    LL ans = 0;
    for (int a = -2e6;a <= 2e6;a++) {
        while (posx + 1 <= n && x[posx + 1] <= a) posx++;
        int l = -2e6,r = y[(n + 1) / 2];
        while (l < r) {
            int mid = l + r >> 1;
            if (check (a,mid)) r = mid;
            else l = mid + 1;
        }
        if (!check (a,l)) continue;
        int pos = l;
        l = y[(n + 1) / 2],r = 2e6;
        while (l < r) {
            int mid = l + r + 1 >> 1;
            if (check (a,mid)) l = mid;
            else r = mid - 1;
        }
        if (!check (a,l)) continue;
//      cout << a << ' ' << "[" << pos << ',' << l << "]    \n";
        ans += l - pos + 1;
    }
    cout << ans << endl;
    return 0;
}