: 枚举 起点, 枚举以该起点为左端点的区间, 计算即可.
对一个区间 , 设 表示前缀和,
需要满足以下条件才能对答案贡献 :
- ,
- .
满足上述条件的总数量即为 .
满足 , 的数量为 ,
满足 (此地不等价于), 数量为 .
则 . (相当于一个简单的容斥)
所以只需考虑 如何求即可.
化简 条件1:
将关于 , 关于 的项 分开.
设 ,
则 .
同理 凭此方法求出, 进而 也就可以得到了.
当以 为参数时, 求 数组的 非严格顺序数对 可转换为求 的 严格逆序数对 , 再使用 总数对数 减去 .
当以 为参数时, 求 数组的 严格顺序数对 可转换为求 的 严格逆序数对.
求逆序对时 下标从 0 开始 . 因为下标 ,.
进行多次归并排序时一定要清空数组, 因为 的值会改变.
#include<bits/stdc++.h>
#define reg register
typedef long long ll;
const int maxn = 500005;
int read(){
char c;
int s = 0, flag = 1;
while((c=getchar()) && !isdigit(c))
if(c == '-'){ flag = -1, c = getchar(); break ; }
while(isdigit(c)) s = s*10 + c-'0', c = getchar();
return s * flag;
}
int N;
int L;
int R;
int A[maxn];
ll B[maxn];
ll sum[maxn];
int tmp[maxn];
ll mergesort(int l, int r){
if(r <= l) return 0;
int mid = l+r >> 1;
int t1 = l, t2 = mid+1, t3 = l;
ll s = mergesort(l, mid) + mergesort(mid+1, r);
while(t1 <= mid && t2 <= r)
if(B[t2] < B[t1]){
s += mid - t1 + 1;
tmp[t3 ++] = B[t2 ++];
}else tmp[t3 ++] = B[t1 ++];
while(t1 <= mid)tmp[t3 ++] = B[t1 ++];
while(t2 <= r) tmp[t3 ++] = B[t2 ++];
for(reg int i = l; i <= r; i ++) B[i] = tmp[i];
return s;
}
int main(){
freopen("game.in", "r", stdin);
freopen("game.out", "w", stdout);
N = read(); L = read(); R = read();
ll Fen_mu = (1+1ll*N)*N >> 1;
for(reg int i = 1; i <= N; i ++) A[i] = read(), sum[i] = A[i] + sum[i-1];
for(reg int i = 1; i <= N; i ++) B[i] = sum[i] - L*i;
ll num_1 = mergesort(0, N);
for(reg int i = 1; i <= N; i ++) B[i] = R*i - sum[i];
B[0] = 0;
ll num_2 = mergesort(0, N);
ll Ans = (Fen_mu-num_1) - num_2;
if(!Ans) printf("0
");
else if(Ans == Fen_mu) printf("1
");
else{
ll gcd = std::__gcd(Ans, Fen_mu);
printf("%lld/%lld
", Ans/gcd, Fen_mu/gcd);
}
return 0;
}