题目分析

题目要求对每个位置 (i)，找到包含 (i) 且长度在 ([l,r]) 之间的连续子序列的最大权值和。直接暴力枚举所有子序列时间复杂度为 (O(n^2))，无法处理 (n=10^5) 的数据，因此需要采用分治结合单调队列优化的方法，将时间复杂度降至 (O(n\log n))。

解题思路

1. 分治策略：将序列递归分成左右两部分，分别求解左右子问题，再处理跨越中点的子序列。
2. 单调队列优化：对于跨越中点的子序列，通过前缀和与单调队列维护区间最大值，快速计算包含中点的合法子序列的最大和。
3. 合并结果：将左右子问题的结果与跨越中点的结果合并，得到每个位置的最终最大值。

代码实现（带注释）

#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(auto i=(a);i<=(b);i++)
#define REP(i,a,b) for(auto i=(a);i>=(b);i--)
#define FORK(i,a,b,k) for(auto i=(a);i<=(b);i+=(k))
#define REPK(i,a,b,k) for(auto i=(a);i>=(b);i-=(k))
#define pb push_back
#define mkpr make_pair
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;

// 最大值更新函数
template<class T>
void ckmx(T &a, T b) {
    a = max(a, b);
}

// 最小值更新函数
template<class T>
void ckmn(T &a, T b) {
    a = min(a, b);
}

// 快速输入输出相关函数
template<class T>
void wrint(T x) {
    if (x < 0) {
        x = -x;
        putchar('-');
    }
    if (x >= 10) wrint(x / 10);
    putchar(x % 10 ^ 48);
}

template<class T>
void read(T &x) {
    x = 0;
    int f = 1;
    char ch = getchar();
    while (!isdigit(ch)) {
        if (ch == '-') f = -1;
        ch = getchar();
    }
    while (isdigit(ch)) {
        x = (x << 1) + (x << 3) + (ch ^ 48);
        ch = getchar();
    }
    x *= f;
}

const int maxn = 1e5 + 5;
int n, x, y;  // x=l, y=r
ll a[maxn];   // 序列数组
ll f[maxn];   // 存储每个位置的答案
ll g[maxn];   // 辅助数组（未使用）
ll lazymx[maxn];  // 临时存储跨越中点的最大值
ll pre[maxn];     // 前缀和数组

// 分治求解函数
void sol(int l, int r) {
    if (l == r) {  // 边界：单个元素
        if (x == 1) ckmx(f[l], a[l]);  // 长度1合法时更新
        return;
    }

    int mid = (l + r) >> 1;
    sol(l, mid);    // 处理左半部分
    sol(mid + 1, r);  // 处理右半部分

    // 处理左半部分点i，右半部分扩展的情况
    {
        // 计算右半部分前缀和
        FOR(i, mid + 1, r) pre[i] = pre[i - 1] + a[i];
        ll suf = 0;  // 左半部分的后缀和（从l到当前i）
        FOR(i, l, mid) suf += a[i];

        deque<int> q;  // 单调队列，维护右半部分前缀和的最大值位置
        // 初始化队列：右半部分长度在[x,y]范围内的前缀和
        FOR(i, max(x, mid + 1 - l + 1), y) {
            if (l + i - 1 > r) break;
            while (!q.empty() && pre[l + i - 1] > pre[q.back()]) q.pop_back();
            q.eb(l + i - 1);
        }
        if (!q.empty()) ckmx(lazymx[l], pre[q.front()] + suf);  // 更新最大值

        // 左移左半部分的起点，维护队列
        FOR(i, l + 1, mid) {
            suf -= a[i - 1];  // 减去移出的元素
            // 弹出超出左边界的位置
            while (!q.empty() && q.front() < i + x - 1) q.pop_front();
            // 加入新的右边界位置
            if (i + y - 1 >= mid + 1 && i + y - 1 <= r) {
                while (!q.empty() && pre[i + y - 1] > pre[q.back()]) q.pop_back();
                q.eb(i + y - 1);
            }
            if (!q.empty()) ckmx(lazymx[i], pre[q.front()] + suf);
        }

        // 传递最大值，更新答案
        FOR(i, l, mid) {
            ckmx(lazymx[i], lazymx[i - 1]);
            ckmx(f[i], lazymx[i]);
        }

        // 重置临时数组
        FOR(i, l, mid) lazymx[i] = -1e18;
        FOR(i, mid + 1, r) pre[i] = 0;
    }

    // 处理右半部分点i，左半部分扩展的情况
    {
        deque<int> q;  // 单调队列，维护左半部分后缀和的最大值位置
        // 计算左半部分后缀和（从i到mid）
        REP(i, mid, l) pre[i] = pre[i + 1] + a[i];
        ll suf = 0;  // 右半部分的前缀和（从mid+1到当前i）
        FOR(i, mid + 1, r) suf += a[i];

        // 初始化队列：左半部分长度在[x,y]范围内的后缀和
        FOR(i, max(x, r - mid + 1), y) {
            if (r - i + 1 < l) break;
            while (!q.empty() && pre[r - i + 1] > pre[q.back()]) q.pop_back();
            q.eb(r - i + 1);
        }
        if (!q.empty()) ckmx(lazymx[r], pre[q.front()] + suf);

        // 右移右半部分的终点，维护队列
        REP(i, r - 1, mid + 1) {
            suf -= a[i + 1];  // 减去移出的元素
            // 弹出超出右边界的位置
            while (!q.empty() && q.front() > i - x + 1) q.pop_front();
            // 加入新的左边界位置
            if (i - y + 1 >= l && i - y + 1 <= mid) {
                while (!q.empty() && pre[i - y + 1] > pre[q.back()]) q.pop_back();
                q.eb(i - y + 1);
            }
            if (!q.empty()) ckmx(lazymx[i], pre[q.front()] + suf);
        }

        // 传递最大值，更新答案
        REP(i, r, mid + 1) {
            ckmx(lazymx[i], lazymx[i + 1]);
            ckmx(f[i], lazymx[i]);
        }

        // 重置临时数组
        FOR(i, mid + 1, r) lazymx[i] = -1e18;
        FOR(i, l, mid) pre[i] = 0;
    }
}

// 主处理函数
void solve(int id_of_test) {
    read(n);
    FOR(i, 0, n + 1) lazymx[i] = f[i] = -1e18;  // 初始化答案为极小值
    read(x); read(y);  // 读入l和r
    FOR(i, 1, n) read(a[i]);  // 读入序列
    sol(1, n);  // 分治求解
    FOR(i, 1, n) printf("%lld ", f[i]);  // 输出答案
    putchar('\n');
}

int main() {
    int T = 1;
    FOR(_, 1, T) solve(_);
    return 0;
}

代码解释

1. 分治策略：将序列递归划分为左右两部分，分别求解子问题后，处理跨越中点的子序列。
2. 单调队列优化：对于跨越中点的子序列，通过前缀和/后缀和结合单调队列，在 (O(n)) 时间内计算最大和。
3. 结果合并：将左右子问题的结果与跨越中点的结果合并，传递最大值以更新每个位置的答案。