Description

题目链接

题目大意:定义一个配对 $(x, y)$ 是好的当且仅当 $\forall i \in [1, n] \land i \ne x, |a_x - a_y| \le |a_x - a_i|$。$m$ 次询问 $[l, r]$ 中好的配对的个数。

Solution

如果将 $\{a_n\}$ 排序,那么 $i$ 只可能跟 $i + 1$ 或 $i - 1$ 配对。

因此可以在 $O(n \log n + n)$ 的时间内处理出所有的好的配对。

接下来考虑询问,不难想到用前缀和的思想回答询问,利用树状数组维护右端点在 $[1, r]$ 内的贡献,然后减去左端点在 $[1, l)$ 内的贡献。

时间复杂度 $O((n + m) \log n)$。

Code

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <cmath>

template <class T>
inline void read(T &x) {
    x = 0;
    int f = 0;
    char ch = getchar();
    while (!isdigit(ch))    { f |= ch == '-'; ch = getchar(); }
    while (isdigit(ch))     { x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar(); }
    x = f ? -x : x;
    return ;
}

typedef unsigned long long uLL;
typedef long long LL;

struct Node {
    int pos, v;
    friend bool operator < (const Node &a, const Node &b) {
        return a.v < b.v;
    }
} a[300010];

struct Query {
    int id, l, r;
    friend bool operator < (const Query &a, const Query &b) {
        if (a.r == b.r)    return a.l < b.l;
        return a.r < b.r;
    }
} q[300010];

struct Pair {
    int l, r;
    Pair() : l(), r() {}
    Pair(const int &il, const int &ir) : l(il), r(ir) {}
    friend bool operator < (const Pair &a, const Pair &b) {
        if (a.r == b.r)    return a.l < b.l;
        return a.r < b.r;
    }
} p[600010];

LL t[300010];
LL ans;
int n, m, cnt;

int lowbit(int x) { return x & -x; }

void modify(int x, LL v) {
    while (x <= n) {
        t[x] += v;
        x += lowbit(x);
    }                                
    return ;
}

LL query(int x) {
    LL s = 0;
    while (x) {
        s += t[x];
        x -= lowbit(x);
    }
    return s;
}

int main() {
    read(n), read(m);
    for (int i = 1; i <= n; ++i)    read(a[i].v), a[i].pos = i;
    for (int i = 1; i <= m; ++i)    read(q[i].l), read(q[i].r), q[i].id = i;
    if (n == 1) {
        puts("0");
        return 0;
    }
    std::sort(a + 1, a + n + 1);
    std::sort(q + 1, q + m + 1);
    p[++cnt] = Pair(std::min(a[1].pos, a[2].pos), std::max(a[1].pos, a[2].pos));
    p[++cnt] = Pair(std::min(a[n].pos, a[n - 1].pos), std::max(a[n].pos, a[n - 1].pos));
    for (int i = 2; i < n; ++i) {
        LL s1 = a[i].v - a[i - 1].v, s2 = a[i + 1].v - a[i].v;
        if (s1 <= s2)    p[++cnt] = Pair(std::min(a[i].pos, a[i - 1].pos), std::max(a[i].pos, a[i - 1].pos));
        if (s1 >= s2)    p[++cnt] = Pair(std::min(a[i].pos, a[i + 1].pos), std::max(a[i].pos, a[i + 1].pos)); 
    }
    std::sort(p + 1, p + cnt + 1);
    for (int i = 1, j = 1; i <= m; ++i) {
        while (p[j].r <= q[i].r && j <= cnt) {
            modify(p[j].l, 1);
            ++j;
        }
        ans += q[i].id * (j - 1 - query(q[i].l - 1));
    }
    printf("%lld\n", ans);
    return 0;
}
Last modification:September 5th, 2021 at 03:09 am