题解：P8991 [北大集训 2021] 出题高手

童年的小翼龙 · 2024-03-23 17:42:55 · 题解

我们充分发扬人类智慧，数学直觉告诉我们，在 a 随机的情况下，我们最终的答案区间不会太长。

于是，我们对于一个固定的右端点，只枚举前 2000 小的区间。对于统计答案，我们从左往右扫描线，计算出考虑前 i 个 a 时，以每个位置作为左端点的最优答案，由于修改和查询次数相差过大，我们可以用分块 O(1)-O(\sqrt n) 地维护。这样就可以在一个比较快的时间内通过除了第三个包之外的所有点。

对于第三个包，由于只有一个询问，所以我们猜测这时候的区间长度会更小，于是我们只枚举长度小于等于 400 的区间，就可以通过第三个包。

时间复杂度 O(n\sqrt n)，正确概率未知。

#include <bits/stdc++.h>
using namespace std;
namespace Slongod{
using ll = long long;
constexpr int N = 5e5+7 , B = 500;
int n , m , a[N] , bl[N];
struct frac{
    ll a , b;
    void yuefen(){ll g = __gcd(a , b); a /= g; b /= g;}
    frac(){a = 0; b = 1;} frac(ll x , ll y){a = x; b = y;}
    bool operator < (const frac&x) const{return a * x.b < x.a * b;}
}ans[N] , now[N] , tag[N];
vector <pair<int,int>> p[N];
void main()
{
    cin >> n; for (int i = 1; i <= n; i++){cin >> a[i]; bl[i] = (i - 1) / B + 1;}
    cin >> m; for (int i = 1 , l , r; i <= m; i++){cin >> l >> r; p[r].push_back({l , i});}
    const int d = (n > 100005 ? 400 : 2000); int t = m;
    for (int i = 1; i <= n; i++) {
        for (int j = i , sum = a[i]; j >= 1 and j > i - d; j-- , sum += a[j]) {
            auto v = frac(1ll * abs(sum) * abs(sum) , i - j + 1);
            if (now[j] < v){now[j] = v;}
            if (tag[bl[j]] < v){tag[bl[j]] = v;}
        }
        for (auto o : p[i]) { t--;
            if (bl[i] == bl[o.first]) {
                for (int j = o.first; j <= i; j++) {
                    ans[o.second] = max(ans[o.second] , now[j]);
                }
            } else {
                for (int j = o.first; bl[j] == bl[o.first]; j++) {
                    ans[o.second] = max(ans[o.second] , now[j]);
                }
                for (int j = bl[o.first] + 1; j < bl[i]; j++) {
                    ans[o.second] = max(ans[o.second] , tag[j]);
                }
                for (int j = i; bl[j] == bl[i]; j--) {
                    ans[o.second] = max(ans[o.second] , now[j]);
                }
            }
        }
        if (!t){break;}
    }
    for (int i = 1; i <= m; i++) {
        ans[i].yuefen();
        cout << ans[i].a << ' ' << ans[i].b << '\n';
    }
}
}int main()
{
    ios :: sync_with_stdio(0);
    cin.tie(0) , cout.tie(0);
    return Slongod :: main(),0;
}