题目分析

给定长度为 $n$ 的序列 $a_1, a_2, \dots, a_n$，对于每个询问 $[ql, qr]$，需要找到子区间 $[l, r] \subseteq [ql, qr]$ 使得 $\frac{(\sum_{i=l}^r a_i)^2}{r-l+1}$ 最大。

核心思路

1. 问题转化

设前缀和 $s_i = \sum_{j=1}^i a_j$，则区间 $[l, r]$ 的特色程度为：

问题转化为：找到 $0 \le l < r \le n$ 使得 $\frac{(s_r - s_l)^2}{r-l}$ 最大。

2. 关键观察

• 决策单调性：最优的 $l$ 对于固定的 $r$ 具有单调性
• 凸壳性质：候选的 $(i, s_i)$ 点构成凸壳，只有凸壳上的点可能成为最优决策
• 随机数据性质：由于 $a_i$ 随机，最优区间长度通常不会太长

算法实现详解

1. 数据结构定义

struct Num {
    ll fm, fz;  // 分子fm，分母fz
    void upd() { // 约分
        if (!fm) return;
        ll G = __gcd(fm, fz);
        fm /= G; fz /= G;
    }
    bool operator < (const Num &rhs) const { // 比较分数
        return fm * rhs.fz < rhs.fm * fz;
    }
};

2. 候选区间生成

// 生成候选区间对 (l, r)
st[top = 1] = 0;
for (int i = 1; i <= n; i++) {
    // 维护单调栈找候选左端点
    while (top && s[st[top]] >= s[i]) top--;
    for (int j = top; j >= 1; j--) {
        if (i - st[j] > L) break;  // 限制区间长度
        vec[i].pb(st[j]);          // 记录候选对
    }
    st[++top] = i;
}

技术细节：

• 分别用递增栈和递减栈处理，确保找到所有可能的极值点
• 限制候选区间长度 $L$ 为 2000（或 400），利用随机性质剪枝

3. 分块处理

struct block {
    Num mx, w[maxB];  // 块内最大值，每个位置的值
    int l, r;         // 块边界
    
    void init(int L, int R, int t) { ... }
    void modify(int x, Num val) { ... }    // 更新位置x
    Num query(int ql, int qr) { ... }     // 查询区间[ql,qr]
} b[maxB << 1];

分块策略：

• 块大小 $B = \min(500, \sqrt{n})$
• 每个块维护内部最大值，支持区间查询

4. 查询处理

Num Query(int l, int r) {
    int p = pos[l], q = pos[r];
    Num res = {0, 1};
    
    if (p == q) 
        res = b[p].query(l, r);
    else {
        res = max(res, b[p].query(l, -1));      // 左碎块
        for (int i = p+1; i <= q-1; i++)        // 整块
            res = max(res, b[i].mx);
        res = max(res, b[q].query(-1, r));      // 右碎块
    }
    return res;
}

算法流程

1. 预处理阶段：

   • 计算前缀和 $s_i$
   • 使用单调栈生成候选区间对 $(l, r)$
   • 初始化分块数据结构

2. 处理询问：

   • 按右端点 $r$ 排序询问
   • 对于每个 $r$，更新所有以 $r$ 为右端点的候选区间
   • 回答所有右端点为 $r$ 的询问

3. 输出答案：

   • 对每个答案分数进行约分
   • 输出分子和分母

关键优化

1. 候选剪枝

• 利用数据随机性，限制候选区间长度
• 减少需要处理的区间对数量

2. 分块优化

• 将序列分块，平衡更新和查询复杂度
• 块内暴力，块间使用预处理的最大值

3. 离线处理

• 按右端点排序询问，利用扫描线思想
• 避免重复计算

复杂度分析

• 候选生成：$O(nL)$，其中 $L$ 为最大候选长度
• 分块处理：$O(n\sqrt{n})$ 预处理
• 查询处理：$O(m\sqrt{n})$ 回答所有询问
• 总复杂度：$O(nL + (n+m)\sqrt{n})$，适合大数据范围

算法标签

主要算法：

• 分块
• 单调栈
• 扫描线

关键技巧：

• 候选区间筛选
• 离线查询处理
• 分数运算优化

问题特征：

• 区间最值查询
• 决策单调性
• 随机数据优化

总结

这道题通过结合单调栈生成候选区间、分块处理区间查询、以及利用数据随机性进行剪枝，高效地解决了大规模数据下的最优区间查找问题。算法体现了对问题性质的深入理解和多种数据结构技巧的综合运用。