P7868 [COCI2015-2016#2] VUDU

· · 题解

题目链接

通过记录

前言

  个人认为这个方法比上面几位都要拉一点，但是很好想，也很好懂。因为我比较拉，为了求清晰一点，所以不管是题解还是代码都写的比较长，望 dalao 见谅。

题目描述

  给你一个长度为 n 的正整数列，请你求出那些平均数大于等于给定值 p 的连续子序列个数。

算法思路

  该题一看好像很简单，再想想好像有点难，但仔细一想也不难。

  首先很容易想到一个常用的事情，我们把每个数都减去 p ，那么那些负数都相当于“拉低平均分”的，正数就是“拉高平均分”的。

  此时，我们记录一个前缀和，比如 sum[i] 表示从 1 到 i 的和。如果是负数，那就是从 1 开始，这一段平均数低了，否则就是符合条件的。

  那么问题来了，怎么处理那些不是以 1 开头的那些连续子序列呢？我们意识到，如果前面有一个前缀和，到后面某一个前缀和，相对的上升了（本体也可以相对不变），就说明这俩中间夹的那些数是正的（也可以是 0），也就是说是“平均分合格”的。这就是一种合法的子序列。

  那么我们怎么去统计这些“相对上升”呢？很明显，这就是求顺序对的个数。

if(你知道顺序对怎么求)
    goto 细节处理
if(你不清楚顺序对是什么，该怎么求)
    goto 求顺序对

求顺序对

  顺序对，就是说一个一个列表中两个数满足 a[i]>a[j] 且 i<j 。那么这两个数就是一组“顺序对”。本体因为可以等于 p，故两个数可以相等。也许不应该叫顺序对而叫非逆序对吧。

  顺序对主要有归并排序和树状数组两个求法，我蒟蒻，只写得来树状数组，这里讲一下下：

  首先开一个值域树状数组。由于本题原数组值域在 -1e9 与 1e9 间，但至多 1e6 个数，所以需要进行离散化。

  按照顺序，在离散化后数组一个数加入前，检测现在的树状数组内小于（本题可以等于）这个值的数有多少个（简单的树状数组区间查询）。那么顺序对的数量就加上这个“个数”。

  因为这些数都是你进来前进来的，而且又比你小，所以有几个数，你就多带来了几个顺序对。

  查询后，你便可以将这个数加进树状数组（简单的树状数组单点修改）。然后就可以开始下一个数的操作了

  这就是求顺序对，简单吧。

细节处理

  如果你刚才就去打了码，会发现过不了样例。问题是出在哪里呢？是这样的。我们求的都是“顺序对”，但是没有去考虑人家一来就是正的，不需要降这种情况。那我们其实也很简单，就是在原序列的第 0 位加上一个 0 ，这样相当于加了一个为 0 的初始状态，可以把那些以来就是正的那些数处理进去了。

代码实现

#pragma GCC optimize(2)//防抄又加速，岂不美哉
#include<bits/stdc++.h>
using namespace std;

#define int long long//记前缀和很有可能就炸了，所以要防祖宗
#define ri register int//卡常小习惯

int a[1000050];//原数列&-p后的数列
struct cma{
    int w,id;
}sum[1000050];//前缀和（处理前）

int lsh[1000050],tim;//离散化后的前缀和

int s[1000050];//树状数组

int n,p,ans;

inline int rd()//快读宝，一款真正智能的语音音箱
{
    int a=0,f=1;
    char c=getchar();
    for(;c<'0'||c>'9';c=getchar()) if(c=='-') f=-1;
    for(;c>='0'&&c<='9';c=getchar()) a=(a<<1)+(a<<3)+c-'0';
    return a*f;
}

bool cmp(cma a,cma b)//离散化前肯定要排序啊
{
    if(a.w==b.w) return a.id<b.id;
    else return a.w<b.w;
}

inline void ls()//进行离散化
{
    int tot=sum[0].w-1;//因为多开了一个0进去，所以从0开始
    for(ri i=0;i<=n;i++)
    {
        if(sum[i].w!=tot) tot=sum[i].w,tim++;
        lsh[sum[i].id]=tim;
    }
    return ;
}

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

inline int ask(int x)//简单区间查询
{
    int res=0;
    while(x>=1)
    {
        res+=s[x];
        x-=lowbit(x);
    }
    return res;
}

inline void addwhole(int x)//简单单点修改
{
    while(x<=tim)
    {
        s[x]++;
        x+=lowbit(x);
    }
}

signed main()
{
    n=rd();

    sum[0].id=0,sum[0].w=0;
    for(ri i=1;i<=n;i++)
        a[i]=rd(),sum[i].w=sum[i-1].w+a[i],sum[i].id=i;

    p=rd();

    for(ri i=1;i<=n;i++)
        sum[i].w-=p*i;//全部减去p

    sort(sum,sum+n+1,cmp);//离散化前的排序

    ls();//离散化

    for(ri i=0;i<=n;i++)
    {
        ans+=ask(lsh[i]);//先统计
        addwhole(lsh[i]);//再加入
    }

    printf("%lld\n",ans);

    return 0;

}