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

程序员文章站 2024-02-26 22:02:22

...

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

$\mathcal{Solution}$

$O(N^2) \ 暴力$ : $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$ .

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

所以只需考虑 $num_1, num_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}>=Lr-Ll+L\ \ \ \ \ \ \ .$

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

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

设 $B_i=S_i-L*i$ ,
则 $num_1 = (B\ 的非严格顺序数对数量)$ .

同理 $num_2$ 凭此方法求出, 进而 $Ans$ 也就可以得到了.

$\mathcal{Addition}$

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

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

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

$\mathcal{Code}$

#include<bits/stdc++.h>
#define reg register

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];
int B[maxn];
int sum[maxn];
int tmp[maxn];

int mergesort(int l, int r){
        if(r <= l) return 0;
        int mid = l+r >> 1;
        int t1 = l, t2 = mid+1, t3 = l;
        int 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();
        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] = L*i - sum[i];
        int num_1 = mergesort(1, N);
        for(reg int i = 1; i <= N; i ++) B[i] = (R+1)*i - sum[i];
        int num_2 = mergesort(1, N);
        int Ans = num_1 - num_2;
        int Fen_mu = (1+N)*N >> 1;
        if(!Ans) printf("0\n");
        else if(Ans == Fen_mu) printf("1\n");
        else{
                int gcd = std::__gcd(Ans, Fen_mu);
                printf("%d/%d\n", Ans/gcd, Fen_mu/gcd);
        }
        return 0;
}