CF1762F Good Pairs 题解

tcqwq · 2026-10-22 20:22:02 · 题解

半小时切了。降蓝！（）

先固定 r，我们考虑刻画满足要求的 (l,r)。有这样的刻画：

我们维护一个区间 [x,y]，初始为 [a_r,a_r]。扫描 i = r \to 1。

• 如果扫到 a_i 时有 a_i > y + k，则 a_i 不合法。否则把 y 替换成 \max(y,a_i)。
• 如果扫到 a_i 时有 a_i < x - k，则 a_i 不合法。否则把 x 替换成 \min(x,a_i)。

相当于，我们记录一个合法区间 [x,y]，倒着扫，每次贪心地尝试扩张这个区间。

显然 y 是我们最大的合法值，x 是最小的合法值，在这个区间外的都不合法，反之，区间内的值都可以通过调整来合法。

由于 x,y 对称，接下来只考虑 y 这一侧如何维护。

合法的 a_i 感觉不好做，正难则反，记 f_r 表示 r 作为右端点，不合法的二元组个数（也因为这一点，我们避免了部分题解会算重的情况）。我们想要快速转移。

对于 r，我们可以找到 a_i \in [a_r,a_r+k] 中最大的编号 i。可以记录每一个数值上次出现的位置，用线段树维护单点修改和区间最大值，从而求出 i。

在 i 这里，我们首次修改了 y \gets a_i，从而再往前的不合法个数就是 f_i。我们只需求出 [i+1,r-1] 的不合法个数即可。而这段区间内，y 一直就等于 a_r。所以有转移：

其中 \operatorname{Count}(l,r,c) 表示 j \in [l,r],\,a_j \ge c 的 j 的个数。

需要在线维护 \operatorname{Count}，上主席树即可。时间空间复杂度均为 O(n \log k)。

代码实现时，由于两颗线段树都是值域上的，可以干脆合并成一颗。空间要开的极限一点。

此外还有一个细节，不能 T 组数据都重建 [1,10^5] 的整颗线段树。所以在输入 T 前就开好 [1,10^5] 的空线段树，并记录当前的节点个数 w。每组数据前把编号 >w 的节点清空即可。

::::info[Code / 1.4s 230MB]

#include<bits/stdc++.h>
using namespace std;
#define N 500009
int n,m,k,qwq,T,V,rt[N],f[N],g[N],a[N];
struct seg{ int l,r,ls,rs,mx,cnt; } tr[N * 19];
void build(int &u,int l,int r){
    u = ++V; tr[u].l = l; tr[u].r = r;
    if(l == r) return;
    int mid = (l + r) >> 1;
    build(tr[u].ls,l,mid); build(tr[u].rs,mid + 1,r);
}
void upd(int &u,int x,int c){
    tr[++V] = tr[u]; u = V;
    if(tr[u].l == tr[u].r){ tr[u].cnt++; tr[u].mx = c; return; }
    if(x <= tr[tr[u].ls].r) upd(tr[u].ls,x,c);
    else upd(tr[u].rs,x,c);
    tr[u].mx = max(tr[tr[u].ls].mx,tr[tr[u].rs].mx);
    tr[u].cnt = tr[tr[u].ls].cnt + tr[tr[u].rs].cnt;
}
int qmx(int u,int l,int r){
    if(l <= tr[u].l && tr[u].r <= r) return tr[u].mx;
    if(r < tr[u].l || tr[u].r < l) return 0;
    return max(qmx(tr[u].ls,l,r),qmx(tr[u].rs,l,r));
}
int qcnt(int u,int l,int r){
    if(l <= tr[u].l && tr[u].r <= r) return tr[u].cnt;
    if(r < tr[u].l || tr[u].r < l) return 0;
    return qcnt(tr[u].ls,l,r) + qcnt(tr[u].rs,l,r);
}
signed main(){
    cin.tie(0); cout.tie(0);
    ios::sync_with_stdio(0);
    m = 100000; build(rt[0],1,m); qwq = V;
    cin>>T;
    while(T--){
        cin>>n>>k;
        for(int i = 1;i <= n;i++) cin>>a[i];
        V = qwq;
        long long ans = 1ll * n * (n + 1) / 2;
        for(int i = 1;i <= n;i++){
            int x = qmx(rt[i - 1],a[i],min(m,a[i] + k));
            f[i] = f[x] + qcnt(rt[i - 1],a[i] + k + 1,m) - qcnt(rt[x],a[i] + k + 1,m);
            int y = qmx(rt[i - 1],max(1,a[i] - k),a[i]);
            g[i] = g[y] + qcnt(rt[i - 1],1,a[i] - k - 1) - qcnt(rt[y],1,a[i] - k - 1);
            rt[i] = rt[i - 1]; upd(rt[i],a[i],i);
            ans -= f[i] + g[i];
            // cout<<"! "<<x<<" "<<y<<"  "<<f[i]<<" "<<g[i]<<endl;
        }
        cout<<ans<<endl;
    }
}

::::