题解 P2717 【寒假作业】

· · 题解

本题有多种方法，此处介绍树状数组与cdq分治两种。

题目分析

看到平均值无脑所有 a_i\leftarrow a_i-k。

于是题目转化为求出满足 1\le x\le y\le n 且 \sum\limits_{i=x}^ya_i\ge0 的 有序数对 (x,y) 的个数。

把 a_i 求一次前缀和（由于后面原 a 数组已经没用所以直接覆盖上去），那么即求所有满足 0\le x<y\le n 且 a_y-a_x\ge0 的有序数对 (x,y) 的个数。

因为 a_y-a_x\ge0，所以 a_x\le a_y，那么求得就是在 [0,n] 范围内 x<y 且 a_x\le a_y 的数对个数，即二维偏序。

解法一 树状数组

类似逆序对的树状数组解法。维护一个数列 A，初始全为 0。从 0 到 n 枚举 i，对每个 i，将答案加上 A 中下标 -\infty 到 a_i 的和。然后将 A 中下标 a_i 加上 1。

注意由于全部减去了 k，a_i 可能为负数，需要离散化。总时间复杂度 O(n\log n)。

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn=1e5+5;
int a[maxn],id[maxn],rk[maxn],bit[maxn],n,k;
LL ans;
bool cmpID(int u,int v){return a[u]<a[v]||(a[u]==a[v]&&u<v);}
int LSB(int x){return x&-x;}
void add(int x){for(;x<=n+1;x+=LSB(x)) ++bit[x];}
int query(int x)
{
    int sum=0;
    for(;x;x-=LSB(x)) sum+=bit[x];
    return sum;
}
int main()
{
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;++i) scanf("%d",a+i); 
    for(int i=1;i<=n;++i) {a[i]+=a[i-1]-k; id[i]=i;}
    sort(id,id+n+1,cmpID);
    for(int i=0;i<=n;++i) rk[id[i]]=i+1;
    for(int i=0;i<=n;++i)
    {
        ans+=query(rk[i]);
        add(rk[i]);
    }
    printf("%lld\n",ans);
    return 0;
}

本人的离散化写法比较奇怪（为了省码量没有使用结构体），勿喷。

rk 数组表示 a_i 在 a 数组中是第几小的。为了避免相同数据，我们在数据相同时加入下标的大小判断。

此外，由于此题中 rk 数组出现了 0，而 0 是不可以出现在树状数组的下标中的，所以我们将 rk 数组全部加上 1。add函数中的上界也要相应的加上1。

解法二 cdq分治

首先我们回忆一下用归什么排序解决逆序对问题的简要步骤：

  1. 将原序列划分为 [l,mid] 和 (mid,r] 两部分。
  2. 递归求解 [l,mid] 和 (mid,r] 两个区间内部的逆序对，并将它们进行排序。
  3. 在合并序列的同时计算跨两个区间的逆序对。

本题其实是一样的 众所周知cdq分治本质上就是归什么排序的扩展延伸

  1. 将原序列划分为 [l,mid] 和 (mid,r] 两部分。
  2. 递归求解 [l,mid] 和 (mid,r] 两个区间内部的偏序，并将它们进行排序。
  3. 在合并序列的同时计算跨两个区间的偏序。

和归什么排序一样，定义 cdq(l,r) 为对区间 [l,r] 进行求解

如果 l=r 则回溯，否则递归求解左右两部分。

    if(l==r) return;
    int mid=(l+r)>>1,i=l,j=mid+1,k=l;
    cdq(l,mid); cdq(mid+1,r);

维护双指针 i,j，分别对应区间的左半部分和右半部分。

对每个 j，将 i 不断右移直到 a_i>a_j （不满足偏序关系）。由于左右两边已经有序，所以 i 不需要清零，总共最多右移 mid-l+1 次，提高了时间效率。

在右移的过程中将 a_i 放入临时数组，完成合并。

那么对这个 j，从 l 到 i-1 都能和 j 构成偏序关系，因此答案加上 (i-1)-(l-1)=i-l。同时将 a_j 放入临时数组。

    for(j=mid+1;j<=r;)
    {
        while(i<=mid&&a[i]<=a[j]) t[k++]=a[i++];
        t[k++]=a[j++];
        ans+=i-l;
    }

操作结束后，右半部分已经进入临时序列，但左半部分可能并没有，所以一定要记得收个尾。然后将临时数组拷贝回 a 数组即可。

    for(;i<=mid;) t[k++]=a[i++];
    for(i=l;i<=r;++i) a[i]=t[i];

cdq函数如下：

void cdq(int l,int r)
{
    if(l==r) return;
    int mid=(l+r)>>1,i=l,j=mid+1,k=l;
    cdq(l,mid); cdq(mid+1,r);
    for(j=mid+1;j<=r;)
    {
        while(i<=mid&&a[i]<=a[j]) t[k++]=a[i++];
        t[k++]=a[j++];
        ans+=i-l;
    }
    for(;i<=mid;) t[k++]=a[i++];
    for(i=l;i<=r;++i) a[i]=t[i];
}

主函数调用 cdq(0,n) 即可。总时间复杂度 O(n\log n)。

后记

上面一行为树状数组的提交记录，下面一行为cdq分治的提交记录。

可以看到cdq完美碾压树状数组。

这不难理解。树状数组因为要离散化，时间差不多有两个 n\log n，空间上多开了两个数组，自带的三件套（LSB,add,query）也导致码量不可避免的变长。

但是，树状数组最大的优点就是：好想，好写，不易写挂。我一开始写的cdq分治犯了几个sb错误，结果过了样例但爆了零。

所以能用树状数组还是尽量用吧。

\texttt{The End.}