题解：CF1762F Good Pairs

· · 题解

按值域分块、DP、线段树。

题意

给定一个长为 n 的序列 a 和一个数 k，定义一个区间 [l,r] 是好的，当且仅当这个区间内存在一个子序列满足：

请求出所有合法的子区间数量。

思路

不妨设 a_l<a_r，当中间某个 a_i<a_l，显然可以删掉 a_i，旁边两个是比 a_i 大的，并且绝对值之差不大于 k，所以可以连上。故只需要考虑 [l,r] 严格递增子序列即可。

直接 DP 方案书会算重，考虑按值域分块。记 \lfloor\frac x k\rfloor 相同的为一个块，相邻两个数一定不会跨越超过 1 个块。对于 a_i，我们只需要找到它前面最近的 j 满足 |a_i-a_j|\le k。这样能到达 a_j 的元素一定也能到达 a_i。

只考虑 a_i 左边的贡献，设 DP 状态 f_{i,0/1/2}，分别表示在前缀 1\sim i 初始和 a_i 一个块、比 a_i 小、比 a_i 大的数能走到 i 的个数。

看一眼 DP 转移。对于 f_{i,0} 很显然可以预处理；对于 f_{i,1} 来说。查询严格小于 a_i 且最近的下标 j，若 a_j 所在的块是 a_i 的前继块，那么有转移 f_{i,1}=f_{i,0}+f_{j,1}；若 a_j 和 a_i 在一个块，那么贡献有重复，需要减掉，则有转移 f_{i,1}=f_{i,0}+f_{j,1}-f_{j,0}。f_{i,2} 的转移同理。查询下标可以对 a_i 开下标的线段树，维护区间 \max。

设右端点为 r，则 f_{r,1}+f_{r,2}-f_{i,0} 为 [1,r] 中一定包含 r 的合法子区间个数，因为 f_{r,1}+f_{r,2} 已经算了两次同块，所以要多减一次。所以答案为 \sum_{i=1}^n(f_{i,1}+f_{i,2}-f_{i,0})。

特判 k=0，是不能分块的，答案应该是所有相等点对。

共 O(n) 次的转移，每次转移有 O(\log n) 查询，总时间复杂度为 O(n\log n)。

再说一下多测的问题。清空的时候只对当前修改过的元素清空。对于线段树来说，可以写动态开点空间换时间，也可以写版本号树，维护版本号 time 和每个节点的最新版本号 ver，pushup 的时候如果 time\ne ver_i，那么就不上传这个儿子的信息。对于 update 来说，每次插入线段树的元素（即下标）一定是递增的，所以不用写严格的取 \max，因为后面插入一定可以覆盖前面的。

::::success[代码]

#include<iostream>
#include<vector>
using namespace std;
const int N=5e5+10;
int T,n,k,buc[N];
long long ans,a[N],f[N][3],maxa;
vector<int>use;
struct segmenttree
{
  int maxx[N*4],ver[N*4],timee=0;
#define ls (u*2)
#define rs (u*2+1)
  void pushup(int u)
  {
    maxx[u]=max(ver[ls]==timee?maxx[ls]:0,ver[rs]==timee?maxx[rs]:0);
    ver[u]=timee;
    return;
  }
  void update(int u,int l,int r,int ql,int qr,int x)
  {
    if(ql<=l&&r<=qr)
    {
      maxx[u]=x;
      ver[u]=timee;
      return;
    }
    int mid=l+(r-l)/2;
    if(ql<=mid)update(ls,l,mid,ql,qr,x);
    if(mid<qr)update(rs,mid+1,r,ql,qr,x);
    pushup(u);
    return;
  }
  int query(int u,int l,int r,int ql,int qr)
  {
    if(ver[u]!=timee)return 0;
    if(ql<=l&&r<=qr)return maxx[u];
    int mid=l+(r-l)/2,res=0;
    if(ql<=mid)res=max(res,query(ls,l,mid,ql,qr));
    if(mid<qr)res=max(res,query(rs,mid+1,r,ql,qr));
    return res;
  }
} t;
signed main()
{
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cin>>T;
  while(T--)
  {
    cin>>n>>k;
    maxa=ans=0;
    ++t.timee;
    for(int i=1; i<=n; ++i)cin>>a[i],maxa=max(maxa,a[i]);
    if(!k)
    {
      for(int i=1; i<=n; ++i)
      {
        if(!buc[a[i]])use.push_back(a[i]);
        ++buc[a[i]];
      }
      for(int i:use)ans+=1ll*buc[i]*(buc[i]+1)/2;
      for(int i:use)buc[i]=0;
      use.clear();
      cout<<ans<<'\n';
      continue;
    }
    for(int i=1,j; i<=n; ++i)
    {
      if(!buc[a[i]/k])use.push_back(a[i]/k);
      ++buc[a[i]/k];
      f[i][0]=1ll*buc[a[i]/k];
      j=0;
      if(max(1ll,a[i]-k)<=a[i]-1)j=t.query(1,1,maxa,max(1ll,a[i]-k),a[i]-1);
      if(j)
      {
        if(a[i]/k==a[j]/k)f[i][1]=f[i][0]+f[j][1]-f[j][0];
        else f[i][1]=f[i][0]+f[j][1];
      }
      else f[i][1]=f[i][0];
      j=0;
      if(a[i]+1<=min(maxa,a[i]+k))j=t.query(1,1,maxa,a[i]+1,min(maxa,a[i]+k));
      if(j)
      {
        if(a[i]/k==a[j]/k)f[i][2]=f[i][0]+f[j][2]-f[j][0];
        else f[i][2]=f[i][0]+f[j][2];
      }
      else f[i][2]=f[i][0];
      ans+=f[i][1]+f[i][2]-f[i][0];
      t.update(1,1,maxa,a[i],a[i],i);
    }
    for(int i:use)buc[i]=0;
    use.clear();
    cout<<ans<<'\n';
  }
  return 0;
}

::::