P5677 配对统计

从值域相邻关系转成区间内二维数点

问题

P5677 [GZOI2017] 配对统计
给定一个元素互不相同的序列。对有序对 $(x,y)$，若对于所有满足 $i\ne x$ 的位置，都有 $\lvert a_y-a_x\rvert\le\lvert a_x-a_i\rvert$，则称它为好配对。
每次询问一个区间 $[l,r]$ 中有多少有序好配对，最后输出第 $i$ 次询问答案乘 $i$ 的总和。

数据规模：$1\le n,m\le3\times10^5$，$1\le a_i\le10^9$，且所有 $a_i$ 互不相同。

首先先看一下什么是好配对，就是说 $a_y$ 是所有其他数中与 $a_x$ 距离最近的一个。放到数轴上，$a_y$ 只可能是 $a_x$ 排序后的前驱或后继，但它们不一定是整个序列中差值最小的一对数。

所以想到了排序，这样每个数可能的好对就是它和它两边的两个数，当然由于询问都是在原数组上的，所以在排序的同时，还需要记录当前元素在原数组的下标。

按值排序后，可以采用离线的想法，把所有可能的好配对都记录下来，然后把配对按右端点 $y$ 排序，询问按 $r$ 排序；扫描到某个询问时，将所以 $y \le r$ 的配对在树状数组上记录，再查询即可。

注：为了把它表示成一条线段，人为规定端点满足 $x<y$，但这不是给有向配对去重。若 $(x,y)$ 与 $(y,x)$ 都是好配对，规范化后仍要保留两份；首尾两个元素则只有一侧候选，需要单独加入。

整体复杂度为 $O((n+m)\log n)$，空间复杂度为 $O(n+m)$。

▶

P5677

struct BIT { /* 模板代码略 */ } bit;

struct Node {
    ll val;
    int id;
    bool operator < ( const Node &oth ) const { return val < oth.val; }
} a[maxn];

struct Query {
    int l, r, id;
    bool operator < ( const Query &oth ) const { return r < oth.r; }
} qs[maxn];

struct Seg {
    int l, r;
    bool operator < ( const Seg &oth ) const { return r < oth.r; }
};

vector<Seg> segs;
void add( int x, int y ) {
    if( x > y ) swap( x, y );
    segs.push_back({ x, y });
}

ll ans[maxn];

void solve( ) {
    int n = read( ), m = read( );

    for( int i = 1; i <= n; ++ i ) {
        a[i].val = read( );
        a[i].id = i;
    }

    sort( a + 1, a + n + 1 );

    if( n == 1 ) {
        cout << 0 << '\n';
        return;
    }

    add( a[1].id, a[2].id );
    add( a[n].id, a[n - 1].id );

    for( int i = 2; i <= n - 1; ++ i ) {
        ll dif1 = a[i].val - a[i-1].val;
        ll dif2 = a[i+1].val - a[i].val;
        if( dif1 <= dif2 ) add( a[i].id, a[i-1].id );
        if( dif2 <= dif1 ) add( a[i].id, a[i+1].id );
    }

    sort( segs.begin( ), segs.end( ) );

    for( int i = 1; i <= m; ++ i ) {
        int l = read( ), r = read( );
        qs[i] = { l, r, i };
    }

    sort( qs + 1, qs + m + 1 );

    bit.init( n );
    int cur = 0;
    for( int i = 1; i <= m; ++ i ) {
        auto [l, r, idx] = qs[i];
        while( cur < (int)segs.size( ) && segs[cur].r <= r ) {
            bit.add( segs[cur].l, 1 );
            cur ++;
        }
        ans[idx] = bit.ask( l, r );
    }

    ll sum = 0;
    for( int i = 1; i <= m; ++ i ) sum += ans[i] * i;
    cout << sum << '\n';
}