AT_abc153_f [ABC153F] Silver Fox vs Monster

模拟赛最后 $15$ 分钟想到的做法。

思路

首先有一个显然的贪心策略：我们放炸弹的地方要尽可能的使这个炸弹能影响到更多的怪上。

那么我们可以将对于一个怪 $i$ 能够影响到它的区间表示出来 $[\max(1,l_i - d),a_i + r]$。

然后将这些区间排个序，可以粗略画出这样的图：

根据上文提到的贪心策略，发现在红线处放炸弹最优。大胆猜测如果对于当前枚举到的怪还需要用炸弹，一定用在能够影响它的区间的右端点。

不难发现这样做是正确的，因为当你处理 $i$ 时，$1 \sim (i - 1)$ 都已经处理完毕，而你已经对区间排序了，所以 $i \sim n$ 的区间一定在 $i$ 之后，放在右端点一定最优。

那么，如何处理 $i$ 还需要用几个炸弹。

首先刚开始时，显然要用 $\lceil \frac{h_i}{a} \rceil$ 个。

在处理了 $1 \sim (i - 1)$ 之后，$i$ 还需要用 $\max(0,\lceil \frac{h_i}{a} \rceil - \Delta)$ 个炸弹，其中 $\Delta$ 表示在处理 $1 \sim (i - 1)$ 时，在能影响当前怪的区间中的炸弹数量。

发现单点修改，区间查询，直接用树状数组维护即可。因为 $x_i$ 较大，需要离散化。

Code

#include <bits/stdc++.h>  
#define re register  
#define int long long  
  
using namespace std;  
  
const int N = 4e5 + 10;  
int n,d,k,m,idx,ans;  
vector<int> p;  
unordered_map<int,int> mp;  
  
struct point{  
    int x;  
    int num;  
  
    friend bool operator <(const point &a,const point &b){  
        return a.x < b.x;  
    }  
}arr[N];  
  
struct sec{  
    int l;  
    int r;  
    int num;  
  
    friend bool operator <(const sec &a,const sec &b){  
        if (a.l != b.l) return a.l < b.l;  
        return a.r < b.r;  
    }  
}s[N];  
  
inline int read(){  
    int r = 0,w = 1;  
    char c = getchar();  
    while (c < '0' || c > '9'){  
        if (c == '-') w = -1;  
        c = getchar();  
    }  
    while (c >= '0' && c <= '9'){  
        r = (r << 3) + (r << 1) + (c ^ 48);  
        c = getchar();  
    }  
    return r * w;  
}  
  
inline int up(int a,int b){  
    if (a % b == 0) return a / b;  
    return a / b + 1;  
}  
  
struct BIT{  
    int tr[N];  
  
    inline int lowbit(int x){  
        return x & -x;  
    }  
  
    inline void modify(int x,int k){  
        if (!x) return;  
        for (re int i = x;i <= m;i += lowbit(i)) tr[i] += k;  
    }  
  
    inline int query(int x){  
        int res = 0;  
        for (re int i = x;i;i -= lowbit(i)) res += tr[i];  
        return res;  
    }  
}tree;  
  
signed main(){  
    n = read();  
    d = read();  
    k = read();  
    for (re int i = 1;i <= n;i++){  
        int h;  
        arr[i].x = read();  
        h = read();  
        arr[i].num = up(h,k);  
    }  
    sort(arr + 1,arr + n + 1);  
    for (re int i = 1;i <= n;i++){  
        p.push_back(max(1ll,arr[i].x - d));  
        p.push_back(arr[i].x + d);  
        s[i] = {max(1ll,arr[i].x - d),arr[i].x + d,arr[i].num};  
    }  
    sort(p.begin(),p.end());  
    unique(p.begin(),p.end());  
    for (auto x:p) mp[x] = ++idx;  
    for (re int i = 1;i <= n;i++){  
        s[i] = {mp[s[i].l],mp[s[i].r],s[i].num};  
        m = max(m,s[i].r);  
    }  
    sort(s + 1,s + n + 1);  
    for (re int i = 1;i <= n;i++){  
        int cnt = s[i].num - tree.query(s[i].r) + tree.query(s[i].l - 1);  
        if (cnt <= 0) continue;  
        ans += cnt;  
        tree.modify(s[i].r,cnt);  
    }  
    printf("%lld",ans);  
    return 0;  
}