卡片游戏 [逆序对_隐 II]

$S o l u t i o n$

$O (N^{2}) <mtext> </mtext> 暴力$ : $O (N)$ 枚举起点, $O (N)$ 枚举以该起点为左端点的区间, 计算即可.

对一个区间 $[l, r]$ , 设 $S_{i}$ 表示前缀和,

需要满足以下条件才能对答案贡献 $1$ :

$\frac{S_{r} - S_{l - 1}}{r - l + 1} > = L$ ,
$\frac{S_{r} - S_{l - 1}}{r - l + 1} < = R$ .

满足上述条件的总数量即为 $A n s$ .
满足 $\frac{S_{r} - S_{l - 1}}{r - l + 1} > = L$ , 的数量为 $n u m_{1}$ ,
满足 $\frac{S_{r} - S_{l - 1}}{r - l + 1} > R$ (此地不等价于 $\frac{S_{r} - S_{l - 1}}{r - l + 1} > = R + 1$ ), 数量为 $n u m_{2}$ .
则 $A n s = n u m_{1} - n u m_{2}$ . (相当于一个简单的容斥)

所以只需考虑 $n u m_{1}, n u m_{2}$ 如何求即可.

化简 条件1: $\frac{S_{r} - S_{l - 1}}{r - l + 1} > = L$

$S_{r} - S_{l - 1} > = L (r - l + 1)$
$S_{r} - S_{l - 1} > = L r - L l + L <mtext> </mtext> .$

将关于 $l$ , 关于 $r$ 的项分开.

$S_{r} - L r > = S_{l - 1} - L (l - 1)$

设 $B_{i} = S_{i} - L * i$ ,
则 $n u m_{1} = (B <mtext> </mtext> 的非严格顺序数对数量)$ .

同理 $n u m_{2}$ 凭此方法求出, 进而 $A n s$ 也就可以得到了.

$A d d i t i o n$

当以 $L$ 为参数时, 求 ${B_{i}}$ 数组的 非严格顺序数对 可转换为求 ${B_{i}}$ 的 严格逆序数对 $t m p$ , 再使用 总数对数 减去 $t m p$ .
当以 $R$ 为参数时, 求 ${B_{i}}$ 数组的 严格顺序数对 可转换为求 ${- B_{i}}$ 的 严格逆序数对.

求逆序对时 下标从 0 开始 . 因为下标 $l - 1 \in [0, N - 1]$ ,.

进行多次归并排序时一定要清空数组, 因为 $B [0]$ 的值会改变.

$C o d e$

#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\n");
        else if(Ans == Fen_mu) printf("1\n");
        else{
                ll gcd = std::__gcd(Ans, Fen_mu);
                printf("%lld/%lld\n", Ans/gcd, Fen_mu/gcd);
        }
        return 0;
}