P7868 VUDU 题解
提供一种不需要使用离散化，从\(0/1\)分数规划的角度推导的思路。然而考试的时候没想到求逆序对挂掉了
分析
题意很清楚了，就是求给出的序列中，对于一段任意长度的连续区间，其元素和的平均数大于等于\(p\)的种数，可以用如下式子来表达：
\[\frac{\sum_{i=l}^{r}a[i]}{r-l+1}\ge p \]推导方法1
当时写出来这个式子，我一眼\(0/1\)分数规划，\(WhichIsKnownAs\)
\[\frac{\sum_{i=l}^{r}a[i]*x[i]}{\sum_{i=l}^{r}b[i]*x[i]}\ge mid \]但是这道题只能选连续的一段，所以\(x[i]\)就不存在了
当然如果你不知道\(0/1\)分数规划，也完全没有关系，往下看就是了。
我们把第一个式子里面的\(r-l+1\)想办法变成第二个式子里面的\(b[i]\)，通过对比很容易发现，我们假设所有的\(b[i]=1\),那么就有：
\[\frac{\sum_{i=l}^{r}a[i]}{r-l+1}\ge p \iff \frac{\sum_{i=l}^{r}a[i]}{\sum_{i=l}^{r}b[i]}\ge p\iff {\sum_{i=l}^{r}a[i]}-p\times {\sum_{i=l}^{r}b[i]}\ge 0\iff \sum_{i=l}^{r}{(a[i]-p\times b[i])}\ge 0 \]不要忘了其中\(b[i]=1\)，于是上面的式子就最终变成了\(\sum_{i=l}^{r}{(a[i]-p)}\ge 0\)
其中\(a[i],p\)都是定值，于是我们记\(v[i]=a[i]-p\)，最终我们就把题意变成了从\(v[i]\)中，选出子段和大于等于\(0\)的方案数
推导方法2
如果您认为上面太麻烦了，那么下面的应该更容易理解了，先回到原来的式子：
\[\frac{\sum_{i=l}^{r}a[i]}{r-l+1}\ge p \]同样的化化简，移移项:
\[\frac{\sum_{i=l}^{r}a[i]}{r-l+1}\ge p \iff\sum_{i=l}^{r}a[i]-(r-l+1)\times p\ge 0 \]如何感性理解上式？
注意到有\(r-l+1\)个\(a[i]\)在求和，还要减去\(r-l+1\)个\(p\)，即判断\(k\)个数减去\(k\)个\(p\)之后的值，是否非负。
那么我们把每个\(p\)均摊到每一个\(a[i]\)上面，就有了我们用第一种方法推导出的：\(\sum_{i=l}^{r}{(a[i]-p)}\ge 0\)了
引入前缀和
问题来到了如何快速求一段区间和？我们自然地想到了前缀和，用\(sum[r]-sum[l-1]\)快速地求出区间和
我们发现对于每一个\(1\le l\le r\le n\)，只要满足\(sum[r]-sum[l-1]\ge 0\)，即\([l,r]\)中元素和大于等于\(0\)，就一定能对答案产生\(1\)的贡献。
这里随便口胡一个\(sum\)序列：\(0,-1,-3,-6,2,3,1,5\)，比如其中\(-1,3\)就可以构成一个答案，表示\([2,5]\)的区间和为\(3-(-1)=4\)
顺序对、逆序对
手玩几组样例就会发现，我们求的其实就是其中顺序对的数量，特别地对于\(l=1\)的情况，\(sum[l-1]=sum[0]=0\)，我们也是需要考虑的,它的实际意义就是\([1,r]\)的区间和。
然后我们再倒过来思考一下，就把顺序对转化成了逆序对。
假设我们把前缀和数组倒过来之后，更具体地说：\(l\le r,sum[l]\ge sum[r]\)就是本题中一个符合条件的情况
小细节
注意要开\(long long\)
Code
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#define int long long
using namespace std;
template <typename T>inline void re(T &x)
{
x=0;int f=1;
char c=getchar();
for(;!isdigit(c);c=getchar()) if(c=='-') f=-f;
for(;isdigit(c);c=getchar()) x=(x<<3)+(x<<1)+(c^48);
x*=f;
}
const int maxn=1e6+100;
int n,a[maxn],sum[maxn],p,rec[maxn],ans[maxn];
long long answer;
void merge(int l,int r)
{
if(l==r)return;
int mid=(l+r)>>1;
int i=l,j=mid+1,cnt=l-1;
merge(l,mid);merge(mid+1,r);
while(i<=mid&&j<=r)
{
if(rec[i]<rec[j])ans[++cnt]=rec[i++];//这个地方一定是<不能是<=
else ans[++cnt]=rec[j++],answer+=mid-i+1;
}
while(i<=mid)
ans[++cnt]=rec[i++];
while(j<=r)
ans[++cnt]=rec[j++];
for(int i=l;i<=r;i++)rec[i]=ans[i];
}
signed main()
{
re(n);
for(register int i=1;i<=n;++i)re(a[i]);
re(p);
for(register int i=1;i<=n;++i)a[i]-=p,sum[i]=sum[i-1]+a[i],rec[n-i+1]=sum[i];
rec[n+1]=sum[0];
merge(1,n+1);
printf("%lld",answer);
return 0;
}
/*
8
3 2 1 7 4 5 6 3
4
22
*/