題目大意

給定一個序列，定義其權值為劃分序列的方案數，使得劃分出來的每個區間 \([l, r]\) 有 \(\max_{i = l}^r {a_i} \leq r - l + 1\) 。對于每個 \(1 \leq i \leq n\) 求只將 \(a_i\) 修改為 \(1\) ，序列的權值。

做法詳解

首先我們先想一想假如不修改 \(a_i\) 怎么做。對于這種序列劃分的問題一般來說都是線性dp ，這道題也不例外，令 \(dp_i\) 表示劃分 \([1, i]\) 的方案數，暴力轉移顯然有

當我們考慮轉移時發現限制轉移的狀態不連續，沒有單調性，十分難處理，所以考慮dp中的暴力優化——CDQ分治優化。

對于 \([l, r]\) ，我們從 \([l, mid]\) 向 \([mid + 1, r]\) 轉移，那么我們首先要處理原本的區間最大值，由于轉移一定是會跨過 \(mid\) 從左向右，那么我們可以維護 \([l, mid]\) 的后綴最大值數組 \(lmx\) 和 \([mid + 1, r]\) 的前綴最大值數組 \(rmx\)，那么我們轉移條件就變成了 \(max\{ lmx_j, rmx_i \} \leq i - j + 1\) ，拆分一下有

移項

我們發現兩個式子左邊只跟 \(i\) 有關，右邊只跟 \(j\) 有關，所以將 \([l, mid]\) 按 \(lmx_j + j - 1\) 排序，然后雙指針保證第一個式子，將 \(j - 1\) 拍到樹狀數組上，對于 \(i\) 查詢樹狀數組 \([1, i - rmx_i]\) 的和，加到 \(dp_i\) 上。

現在不帶修改做完了，我們想想帶修改的怎么做。我們發現將 \(a_i\) 修改為 \(1\) 相當于是將 \(i\) 的限制給消削掉了，所以答案中每一種方案一定包含什么都不改的序列的劃分方案，所以我們考慮增加了那些方案。

首先我們不可能將 \(a_i\) 改了后再跑一遍dp（這不廢話），同時對于劃分序列正著dp倒著dp沒有影響，\(i\) 也只包含與一個區間，所以我們可以預處理兩個dp數組 \(f_i\) 和 \(g_i\) 分別表示 \([1, i]\) 的劃分方案數和 \([i, n]\) 的劃分方案數。

那么增加的方案顯然有 \(\sum_{l = 1}^i \sum_{r = i}^n f_{l - 1} g_{r + 1} \times [\max_{j = l}^r \{ a_j \} = a_i > r - l + 1 \wedge \text{secondmax}_{j = l}^r \{ a_j \} \leq r - l + 1]\) 。

同樣，這個條件很難直接做，我們就把其扔到CDQ里面考慮。對于 \([l, r]\) ，我們依照預處理dp那樣維護 \(lmx\) ，\(rmx\) ，再額外維護 \(selmx\) ，\(sermx\) ，以及 \(p_i\) 表示 \(i\) 的前綴/后綴最大值位置。考慮枚舉 \(l/r\)（以 \(r\) 為例），首先，我們可以肯定的是當前所算出的方案數增加量是加在 \(p_r\) 的答案上的，然后，因為我們要同時保證 \(a_{p_i} > r - l + 1 \wedge \text{secondmax}_{j = l}^r \{ a_j \} \leq r - l + 1\) ，如果我們把 \(r - rmx_r \geq l - 1\) 拉出來排序那就需要跑兩遍，還要加到同一個計算點上@#!%^&#@*……總之，就是S上加S，所以我們把 \(r \geq lmx_l + l - 1\) 拉出來排序，然后將 \(l - 1\) 拍到樹狀數組上，權值為 \(f_{l - 1}\)，查詢時就可以簡單地查詢樹狀數組上 \((r - rmx_r, r - sermx_r]\) 的和，加到 \(ans_{p_r}\) 上即可。

就這樣

for (int i = mid + 1, j = l;i <= r;++i) {
    while (j <= mid && lmx[id[j]] + id[j] <= i + 1) {
        BIT.change(id[j], f[id[j] - 1]);
        stk[++top] = id[j];
        ++j;
    }
    trans(ans[p[i]], (BIT.query(i - rsemx[i] + 1) - BIT.query(i - rmx[i] + 1) + mod) * g[i + 1] % mod);
}

Solution

代碼和講的有些 \(+1\)、\(-1\) 的位置不一樣，讀者移下項就可以發現于解法中式子是一樣的。

還有代碼輸入輸出跟本題有些不同，因為筆者是在另一個地方做的，見諒。

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 2e5 + 5;
const int mod = 998244353;
int n, q;
int a[N];
LL f[N], g[N];
#define lowbit(x) (x & -x)
inline void trans(LL& x, LL y) { x = (x + y) % mod; }
struct BinaryTree {
    LL c[N << 1];
    inline void change(int x, LL k) { for (;x <= n + 1;x += lowbit(x)) trans(c[x], k); }
    inline void clean(int x) { for (;x <= n + 1;x += lowbit(x)) c[x] = 0; }
    inline LL query(int x) {
        LL ret = 0;
        for (;x > 0;x -= lowbit(x)) trans(ret, c[x]);
        return ret;
    }
}BIT;
int id[N], lmx[N], rmx[N], lsemx[N], rsemx[N], p[N];
inline void reset(int l, int r) { for (int i = l;i <= r;++i) id[i] = i; }
inline bool cmp(int i, int j) { return lmx[i] + i < lmx[j] + j; }
inline bool cmp2(int i, int j) { return i - rmx[i] + 1 < j - rmx[j] + 1; }
int stk[N], top;
inline void solve(int l, int r, LL* dp) {
    if (l == r) {
        if (a[l] == 1) trans(dp[l], dp[l - 1]);
        return;
    }
    int mid = l + r >> 1;
    solve(l, mid, dp);
    lmx[mid] = a[mid];
    for (int i = mid - 1;i >= l;--i) lmx[i] = max(lmx[i + 1], a[i]);
    rmx[mid + 1] = a[mid + 1];
    for (int i = mid + 2;i <= r;++i) rmx[i] = max(rmx[i - 1], a[i]);
    sort(id + l, id + mid + 1, cmp);
    for (int i = mid + 1, j = l;i <= r;++i) {
        while (j <= mid && lmx[id[j]] + id[j] <= i + 1) {
            BIT.change(id[j], dp[id[j] - 1]);
            stk[++top] = id[j];
            ++j;
        }
        trans(dp[i], BIT.query(i - rmx[i] + 1));
    }
    reset(l, mid);
    while (top > 0) BIT.clean(stk[top--]);
    solve(mid + 1, r, dp);
}
LL ans[N], d[N];
inline void solve2(int l, int r) {
    if (l == r) return trans(ans[l], (a[l] > 1) * f[l - 1] * g[l + 1]);
    int mid = l + r >> 1;
    solve2(l, mid);
    solve2(mid + 1, r);
    lmx[mid] = a[mid];
    lsemx[mid] = 0;
    p[mid] = mid;
    for (int i = mid - 1;i >= l;--i) {
        lmx[i] = lmx[i + 1], lsemx[i] = lsemx[i + 1];
        p[i] = p[i + 1];
        if (a[i] > lmx[i]) lsemx[i] = lmx[i], lmx[i] = a[i], p[i] = i;
        else if (a[i] > lsemx[i]) lsemx[i] = a[i];
    }
    rmx[mid + 1] = a[mid + 1];
    p[mid + 1] = mid + 1;
    rsemx[mid + 1] = 0;
    for (int i = mid + 2;i <= r;++i) {
        rmx[i] = rmx[i - 1], rsemx[i] = rsemx[i - 1];
        p[i] = p[i - 1];
        if (a[i] > rmx[i]) rsemx[i] = rmx[i], rmx[i] = a[i], p[i] = i;
        else if (a[i] > rsemx[i]) rsemx[i] = a[i];
    }
    sort(id + l, id + mid + 1, cmp);
    for (int i = mid + 1, j = l;i <= r;++i) {
        while (j <= mid && lmx[id[j]] + id[j] <= i + 1) {
            BIT.change(id[j], f[id[j] - 1]);
            stk[++top] = id[j];
            ++j;
        }
        trans(ans[p[i]], (BIT.query(i - rsemx[i] + 1) - BIT.query(i - rmx[i] + 1) + mod) * g[i + 1] % mod);
    }
    reset(l, mid);
    while (top > 0) BIT.clean(stk[top--]);
    sort(id + mid + 1, id + r + 1, cmp2);
    for (int i = mid, j = r;i >= l;--i) {
        while (j > mid && id[j] - rmx[id[j]] + 1 >= i) {
            BIT.change(id[j] + 1, g[id[j] + 1]);
            stk[++top] = id[j] + 1;
            --j;
        }
        trans(ans[p[i]], ((BIT.query(n + 1) - BIT.query(i + lsemx[i] - 1) + mod) - (BIT.query(n + 1) - BIT.query(i + lmx[i] - 1)) + mod) * f[i - 1] % mod);
    }
    reset(mid + 1, r);
    while (top > 0) BIT.clean(stk[top--]);
}
int main() {
    freopen("divide.in", "r", stdin);
    freopen("divide.out", "w", stdout);
    scanf("%d%d", &n, &q);
    for (int i = 1;i <= n;++i) scanf("%d", &a[i]);
    for (int i = 1;i <= n;++i) id[i] = i;
    f[0] = g[0] = 1;
    solve(1, n, f);
    for (int i = 1;i <= n;++i) trans(ans[i], f[n]);
    reverse(a + 1, a + n + 1);
    solve(1, n, g);
    reverse(a + 1, a + n + 1);
    reverse(g + 1, g + n + 1);
    g[n + 1] = 1;
    solve2(1, n);
    while (q--) {
        int x;scanf("%d", &x);
        printf("%lld\n", ans[x]);
    }
    return 0;
}