题解：AT_abc444_e [ABC444E] Sparse Range

· · 题解

分析性质

  1. 我们发现 l 从后往前枚举 r 是单调不递增的，所以我们可以进行双指针。
  2. 我们发现满足题目条件的充要条件是任意两个 [a_i-d+1,a_i+d-1] 区间是不相交的，其中 i 在区间 [l,r] 中，所以我们可以使用线段树进行维护。

其他问题

记得离散化。

Code

所以代码如下：

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int N = 4e5+10;
const int inf = 2e9;

int n, a[N], d;
int b[N], c[N];
int p[N], q[N];

int sum[4*N];

void doChange(int k, int l, int r, int x, int dx) {
    if (r < x || x < l) return ;
    if (l == r) {
        sum[k] += dx;
        return ;
    }
    int mid = (l + r) >> 1;
    doChange(k*2, l, mid, x, dx);
    doChange(k*2+1, mid+1, r, x, dx);
    sum[k] = sum[k*2]+sum[k*2+1];
}

int doQuery(int k, int l, int r, int x, int y) {
    if (r < x || y < l) return 0;
    if (x <= l && r <= y) return sum[k];
    int mid = (l + r) >> 1;
    return doQuery(k*2, l, mid, x, y) + doQuery(k*2+1, mid+1, r, x, y);
}

signed main() {
    cin >> n >> d;
    for (int i = 1;i<= n;i++) {
        cin >> a[i], b[i] = a[i];
    }
    sort(b+1, b+n+1);
  // 进行离散化
    int m = unique(b+1, b+n+1)-b-1;
    for (int i = 1;i<= n;i++) {
        c[i] = lower_bound(b+1, b+m+1, a[i])-b;
    } 
    for (int i = 1;i<= n;i++) {
        int l = a[i]-d+1, r = a[i]+d-1;
        l = lower_bound(b+1, b+m+1, l)-b, r = upper_bound(b+1, b+m+1, r)-b-1;
        if (r < l) r = l;
        p[i] = l, q[i] = r;
    }
    int ans = 0;
    int l = n, r = n;
    while (l >= 1) {
        while (r - 1 >= l && doQuery(1, 1, n, p[l], q[l]) >= 1) { // 判断不合法
            doChange(1, 1, n, c[r], -1);
            r--;
        }
        doChange(1, 1, n, c[l], 1);
        ans += (r-l+1);
        l--;
    }
    cout << ans << endl;
    return 0;
}