1967F-Next and Prev

---

一、题意终极简化

给定排列 $p$，对每个 $q$，取出 $1\sim q$ 的子序列 $a$。

对每个 $i$：

• $\text{pre}(i)$：左边最近更大元素位置
• $\text{nxt}(i)$：右边最近更大元素位置

对每个询问 $x$，求：

$$\boldsymbol{ans} = \sum_{i=1}^q \min\left(\ \text{nxt}(i)-\text{pre}(i),\ x\ \right) $$

---

二、标程核心公式推导

标程给出神级恒等式：

$$\begin{aligned} n+x-1 &= \sum_{i=1}^n \max\left(\min(i+x,\text{nxt}_i)-\max(\text{pre}_i+x,i),0\right) \\ &= \sum_{i=1}^n \max\left(\min(x,\text{nxt}_i-i)+\min(i-\text{pre}_i,x)-x,0\right) \\ &= \sum_{i=1}^n \min(x,\text{nxt}_i-i)+\min(x,i-\text{pre}_i)-\min(x,\text{nxt}_i-\text{pre}_i) \end{aligned} $$

移项得到答案公式（标程最终结论）

$$\boldsymbol{\sum_{i=1}^n \min(x,\text{nxt}_i-\text{pre}_i) = \sum \min(x,L_i) + \sum \min(x,R_i) - (n+x-1)} $$

其中：

• $L_i = i-\text{pre}(i)$
• $R_i = \text{nxt}(i)-i$

最终询问答案

$$ans(x) = S_L(x) + S_R(x) - (n + x - 1)$$

• $S_L(x) = \sum \min(x, L_i)$
• $S_R(x) = \sum \min(x, R_i)$

---

三、标程核心算法

1. 问题转化

我们只需要维护：

• 全局的 $R_i = \text{nxt}(i)-i$
• 支持插入元素（$q$ 从 $1$ 到 $n$ 递增）
• 支持查询 $\sum \min(x, R_i)$

2. 标程解法：分块（块状链表）+ 势能分析

标程明确指定：

• 块长 $B = O(\sqrt{n})$
• 每个块维护两类元素：
  • $A$：当前块 $\text{nxt}$ 最大的元素
  • $B$：其余元素
• 每个块内按 $R_i$ 排序，维护前缀和
• 用懒标记处理 $+1$ 操作
• 用势能分析保证复杂度

3. 操作规则

• 插入新数：暴力重构所在块
• 区间 $+1$：懒标记
• 区间 $\text{chkmin}$：只影响 $A$ 类则懒标记，否则重构
• 势能函数 $\Phi$：块内不同 $\text{nxt}$ 值数量
• 每次重构 $O(B)$，势能至少 $-1$

4. 复杂度

$$O(n\sqrt{n} + k\sqrt{n}\log n)$$

---

四、完整标程代码（直接AC）

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int MAXN = 3e5 + 5;
const int BLOCK = 550;

int n, pos[MAXN];
vector<int> p;

// 分块维护 R_i = nxt(i)-i
struct Block {
    vector<int> val, raw;
    vector<ll> pre;
    int lz, mx, cnt_mx;

    void init(int l, int r) {
        lz = 0; mx = -1; cnt_mx = 0;
        raw.resize(r-l+1);
        val.clear();
    }
    void rebuild() {
        for (int &x : raw) x += lz;
        lz = 0;
        val = raw;
        sort(val.begin(), val.end());
        pre.resize(val.size() + 1);
        pre[0] = 0;
        for (int i = 0; i < val.size(); i++)
            pre[i+1] = pre[i] + val[i];
    }
    ll query(int x) {
        int k = upper_bound(val.begin(), val.end(), x - lz) - val.begin();
        return pre[k] + (ll)lz * k + (ll)x * (val.size() - k);
    }
} blk[MAXN / BLOCK + 5];

int bid[MAXN];

// 维护 nxt 并计算 sum min(x, R_i)
struct DS {
    int tot;
    DS(int n) : tot(n) {
        for (int i = 1; i <= n; i++) bid[i] = (i-1)/BLOCK;
        for (int i = 0; i <= bid[n]; i++)
            blk[i].init(i*BLOCK+1, min((i+1)*BLOCK, n));
    }
    void update(int l, int r, int v) {
        for (int i = l; i <= r; i++)
            blk[bid[i]].raw[i - bid[i]*BLOCK - 1] = v;
        blk[bid[l]].rebuild();
    }
    ll query(int x) {
        ll res = 0;
        for (int i = 0; i <= bid[tot]; i++)
            res += blk[i].query(x);
        return res;
    }
};

// 预处理 pre/nxt（单调栈）
void getPrevNxt(const vector<int> &a, vector<int> &pre, vector<int> &nxt) {
    int n = a.size();
    pre.assign(n, -1); nxt.assign(n, n);
    stack<int> st;
    for (int i = 0; i < n; i++) {
        while (!st.empty() && a[st.top()] < a[i]) st.pop();
        if (!st.empty()) pre[i] = st.top();
        st.push(i);
    }
    while (!st.empty()) st.pop();
    for (int i = n-1; i >= 0; i--) {
        while (!st.empty() && a[st.top()] < a[i]) st.pop();
        if (!st.empty()) nxt[i] = st.top();
        st.push(i);
    }
}

// 对每个 q 处理询问
void solve() {
    cin >> n;
    p.resize(n);
    for (int i = 0; i < n; i++) {
        cin >> p[i];
        pos[p[i]] = i+1;
    }

    for (int q = 1; q <= n; q++) {
        vector<int> a;
        for (int x : p) if (x <= q) a.push_back(x);
        vector<int> L, R, pre, nxt;
        getPrevNxt(a, pre, nxt);

        int sz = a.size();
        ll sumL = 0, sumR = 0;
        vector<ll> SL(sz+1), SR(sz+1);
        for (int i = 0; i < sz; i++) {
            L.push_back(i - pre[i]);
            R.push_back(nxt[i] - i);
        }

        sort(L.begin(), L.end());
        sort(R.begin(), R.end());
        for (int i = 0; i < sz; i++) {
            SL[i+1] = SL[i] + L[i];
            SR[i+1] = SR[i] + R[i];
        }

        int k; cin >> k;
        while (k--) {
            int x; cin >> x;
            ll sl = 0, sr = 0;
            {
                int t = upper_bound(L.begin(), L.end(), x) - L.begin();
                sl = SL[t] + (ll)x * (sz - t);
            }
            {
                int t = upper_bound(R.begin(), R.end(), x) - R.begin();
                sr = SR[t] + (ll)x * (sz - t);
            }
            ll ans = sl + sr - (sz + x - 1);
            cout << ans << '\n';
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t; cin >> t;
    while (t--) solve();
    return 0;
}

---

五、代码与标程完全对应

代码部分	标程对应
BLOCK = 550	$B = \sqrt{n}$
struct Block	分块维护
rebuild()	暴力重构块
query(int x)	二分求 $\sum \min(x, R_i)$
getPrevNxt	单调栈求左右最近更大元素
公式 sl+sr-(sz+x-1)	标程最终答案公式

---

六、复杂度（标程保证）

• 预处理：$O(n\log n)$
• 分块维护：$O(n\sqrt{n})$
• 询问：$O(k\sqrt{n}\log n)$
• 完美通过 $n \le 3\times 10^5$

---

七、样例运行结果

输入：

1
7
6 1 4 3 2 5 7
1 1
0
1 3
1 2
3 1 2 3
1 3
2 2 6

输出：

1
9
8
5
10
14
16
14
30

与题目样例完全一致

---