牛客多校4.J.Average 数学+二分

牛客多校4.J.Average

设子矩阵横向起点终点 l 1 ,   r 1 l_1,\ r_1 l1​, r1​，纵向起点终点 l 2 ,   r 2 l_2,\ r_2 l2​, r2​，则子矩阵平均值可以表示为： ∑ i = l 1 r 1 ∑ j = l 2 r 2 W [ i ] [ j ] ( r 1 − l 1 + 1 ) × ( r 2 − l 2 + 1 ) = ∑ i = l 1 r 1 ∑ j = l 2 r 2 a i + b j ( r 1 − l 1 + 1 ) × ( r 2 − l 2 + 1 ) = ( r 2 − l 2 + 1 ) ∑ i = l 1 r 1 a i + ( r 1 − l 1 + 1 ) ∑ j = l 2 r 2 b i ( r 1 − l 1 + 1 ) × ( r 2 − l 2 + 1 ) = ∑ i = l 1 r 1 a i r 1 − l 1 + 1 + ∑ j = l 2 r 2 b i r 2 − l 2 + 1 \begin{aligned} & \sum^{r_1}_{i = l_1} \sum^{r_2}_{j = l_2} \frac{W[i][j]}{(r_1 - l_1 + 1) \times(r_2 - l_2 + 1)} \\ &=\sum^{r_1}_{i = l_1} \sum^{r_2}_{j = l_2} \frac{a_i + b_j}{(r_1 - l_1 + 1) \times(r_2 - l_2 + 1)} \\ &=\frac{(r_2 - l_2 + 1)\sum^{r_1}_{i = l_1}a_i + (r_1 - l_1 + 1) \sum^{r_2}_{j = l_2}b_i }{(r_1 - l_1 + 1) \times(r_2 - l_2 + 1)} \\ &=\frac{\sum^{r_1}_{i = l_1}a_i}{r_1 - l_1 + 1}+\frac{\sum^{r_2}_{j = l_2}b_i}{r_2 - l_2 + 1} \end{aligned} ​i=l1​∑r1​​j=l2​∑r2​​(r1​−l1​+1)×(r2​−l2​+1)W[i][j]​=i=l1​∑r1​​j=l2​∑r2​​(r1​−l1​+1)×(r2​−l2​+1)ai​+bj​​=(r1​−l1​+1)×(r2​−l2​+1)(r2​−l2​+1)∑i=l1​r1​​ai​+(r1​−l1​+1)∑j=l2​r2​​bi​​=r1​−l1​+1∑i=l1​r1​​ai​​+r2​−l2​+1∑j=l2​r2​​bi​​​ 分别对两部分求极值即可。对于求极值可以使用二分查找求解。

#include 
#define int long long
#define mod 1000000007
using namespace std;
int n, m, x, y, t, tot;
double ans;
double a[200005], b[200005], sum[200005];

double erfen(double *a, int n, int f){
    double l = -1e6, r = 1e6;
    while (r - l > 1e-10){
        double mid = (l + r) / 2;
        for (int i = 1; i  m >> x >> y;
    for (int i = 1; i > a[i];
    ans += erfen(a, n, x);
    for (int i = 1; i > a[i];
    ans += erfen(a, m, y);
    cout