A

由题意，设 b 的前两个数为 。那么公差最多有 9 种，即 。因此暴力枚举并判断即可。

B

可以用树形 DP，更简单的做法是发现答案等于所有边权和的两倍减去树的直径。

C

考虑固定右端点 ，计算可行的区间左端点数目。发现区间最大值随着左端点左移单调不减，区间最小值随着左端点左移单调不增。这表明如果对于某个左端点 ，区间 符合条件，那么对任意 ， 也满足。

因此预先建立 ST 表，然后枚举右端点，二分出最靠右的可行左端点即可统计答案。

int f[100005][18], g[100005][18], logg;
void build_ST(int *a, int n){
    for(int i = 1; i <= n; ++i)
        f[i][0] = g[i][0] = a[i - 1];
    logg = 1;
    while ((1 << logg) < n) logg++;
    for (int i = 1; i < logg; ++i){
        int p = (1 << i);
        for (int j = 1; j + p - 1 <= n; ++j)
            f[j][i] = max(f[j][i - 1], f[j + (p >> 1)][i - 1]), 
            g[j][i] = min(g[j][i - 1], g[j + (p >> 1)][i - 1]);
    }
    f[1][logg] = max(f[1][logg - 1], f[1 << (logg - 1)][logg - 1]);
    g[1][logg] = min(g[1][logg - 1], g[1 << (logg - 1)][logg - 1]);
}
int getLog(int x){
    if(x <= 2) return 0;
    if(x <= 4) return 1;
    if(x <= 8) return 2;
    if(x <= 16) return 3;
    if(x <= 32) return 4;
    if(x <= 64) return 5;
    if(x <= 128) return 6;
    if(x <= 256) return 7;
    if(x <= 512) return 8;
    if(x <= 1024) return 9;
    if(x <= 2048) return 10;
    if(x <= 4096) return 11;
    if(x <= 8192) return 12;
    if(x <= 16384) return 13;
    if(x <= 32768) return 14;
    if(x <= 65536) return 15;
    if(x <= 131072) return 16;
}
bool query(int l, int r){
    int od = getLog(r - l + 1);
    int mmaxi = max(f[l][od], f[r - (1 << od) + 1][od]);
    int mmini = min(g[l][od], g[r - (1 << od) + 1][od]);
    return mmaxi >= 2 * mmini;
}
class Solution {
    long long ans;
public:
    long long MaxMin(int* array, int arrayLen) {
        ans = 0;
        build_ST(array, arrayLen);
        for (int i = 0; i < arrayLen; ++i){
            int l = -1, r = i;
            while (r > l){
                int mid = (l + r + 1) >> 1;
                if (query(mid + 1, i + 1))
                    l = mid;
                else r = mid - 1;
            }
            ans += l + 1;
        }
        return ans;
    }
};