分享一种想了一下午，发现是一个不好想也不好做的方法。

我们首先想到的大概率是一道 dp 题。

但是在定义状态之前，我们考虑把所有的限制条件列出来，方便思考。

对于我们选择的 $k$，有：

$$\max_{i=1}^n p_i \le k \le n$$

当然，这里要求 $p_i$ 不能为 $-1$。

对于我们需要构造的序列 $t$，有：

• $t_i \le t_{i+1}(i < k)$；
• $t_i < i$；
• $t_{p_i} < i$；
• $t_{p_i+1} \ge i$。

我们发现，$p_i$ 的限制如果不预处理，那么就不能 $O(1)$ 得到，所以考虑将 $p_i$ 或 $p_i+1$ 作为下标，使 $t_i$ 可以轻松查询到其范围。

具体来说可以这样写：

for (int i = 1;i<= n;i++) {
    Min[i] = 0, Max[i] = i-1;
}
for (int i = 1;i<= n;i++) {
    if (p[i] == -1) continue;
    Max[p[i]] = min(Max[p[i]], i-1);
    Min[p[i]+1] = max(Min[p[i]+1], i);
}

$Max$ 和 $Min$ 分别代表亚历山大与第 $i$ 号参赛者沟通的时间的上界和下界。

显然，我们还需要保证 $Min_i$ 不降。

现在，我们定义 $dp_{i, j}$ 表示前 $i$ 个人 $t_i = j$ 可以得到的最大收益是 $dp_{i, j}$。

那么很明显，转移方程就是：

$$dp_{i, j} = \max_{k = Min_{i-1}}^{\min(Max_{i-1}, j)} dp_{i-1, k} + a_i + j \times b_i$$

我们发现，这个就是一个前缀最小值，所以重新定义 $dp_{i, j}$ 为前 $i$ 个人 $t_i \in [Min_i, j]$ 可以得到的最大收益是 $dp_{i, j}$。

显然转移方程有：

$$dp_{i, j} = \begin{cases} dp_{i-1, \min(Max_{i-1}, j)} + a_i + j \times b_i & j = Min_i \\ \max(dp_{i,j-1},dp_{i-1, \min(Max_{i-1}, j)} + a_i + j \times b_i) & j \ne Min_i \end{cases}$$

这个时候，我们发现优化不下去了。

怎么办呢？

我们发现，对于 $dp_{i, j}$ 来说，当 $i$ 相同时具有凸性。

既然具有凸性，我们考虑差分，有：

$$\begin{aligned} dp_{i, j}-dp_{i,j-1} &= dp_{i-1, \min(Max_{i-1}, j)} + a_i + j \times b_i - dp_{i-1, \min(Max_{i-1}, j-1)} + a_i + (j-1) \times b_i \\ &= dp_{i-1, \min(Max_{i-1}, j)} - dp_{i-1, \min(Max_{i-1}, j-1)} + b_i \end{aligned}$$

发现，这个的差分就是上一个差分加 $b_i$。

那么我们定义 $d_{i, j} = dp_{i, j} - dp_{i, j-1}$。

但不是还有一个 $\max dp_{i,j-1}$ 的操作嘛，所以我们可以得出 $d_{i, j}$ 一定不小于 $0$。

所以说，$d_{i, j}$ 的转移就是 $\max(0, d_{i-1, j} + b_i)$。

但是这个东西需要保证 $j \ne Min_i$，对于 $j = Min_i$，很明显有 $dp_{i, j} = (\sum_{k=Min_{i-1}}^{\min(j,Max_{i-1})} d_{i-1, j}) + a_i + j \times b_i$。

我们发现，这个可以用线段树维护 $d_{i, j}$ 的值，而且 $d_{i, j} < 0$ 的时候是一段后缀。

具体来说，可以写出：

int ans = -inf;
if (low == 0) ans = 0;
for (int i = 1;i<= n;i++) {
    if (Min[i] > Max[i]) break;
    int lPre = Min[i-1], rPre = Max[i-1];
    int First = doQuery(1, 0, n, lPre, min(rPre, Min[i]));
    doChangeClear(1, 0, n, 0, Min[i], 0);
    doChangeClear(1, 0, n, Max[i]+1, n, 0);
    doChangeAdd(1, 0, n, Min[i], Min[i], First + a[i] + Min[i] * b[i]);
    doChangeAdd(1, 0, n, Min[i]+1, Max[i], b[i]);
    if (b[i] < 0) { // 保证 d[i][j] 为非负整数
        int k = getSmall(1, 0, n, Min[i]+1, Max[i]);
        if (k != -1) doChangeClear(1, 0, n, k, Max[i], 0);
    }
    if (i >= low) { // low 表示的就是 max p[i]
        ans = max(ans, doQuery(1, 0, n, Min[i], Max[i]));
    }
}   

这个就是一个很大常数的 $O(n\log(n))$，优化的好的话，大概率是可以过的，但是作者没过（菜），只拿到了 $n \le 10^5$ 的分。

所以我们继续优化，我们发现上面的代码就是有 $3$ 种操作。

其中，每次对当前区间 $[Min_i+1, Max_i]$ 加 $b_i$；以及每次把小于 $0$ 的差分强制变成 $0$。

我们考虑将线段树的值变成一个一个块，用双端队列实现上面的操作。

• 左端点移动，就是 $Min_i$ 增大了，这个就是直接从双端队列的头部不断丢块，把丢弃的值累计到 $d_{i,Min_i}$。
• 右端点移动，如果缩小，就像等于是从尾部丢弃块；如果扩大，就是从尾部追加一段值为 $0$ 的块。
• 全局加，我们可以维护一个全局懒标记就行了。
• 清除负数，因为负数必定在队尾，直接从尾部把值 $< 0$ 的块一整个一整个地弹掉，然后补上一个值为 $0$ 的大块就行了。

我们发现，每次只会向双端队列里加入至多 $2$ 个块，所以加块和丢块的次数不会超过 $2n$ 次，摊还分析得到时间复杂度为 $O(n)$。

还有些注意的，我们是不用加 $d_{i, Min_i}$，首先是不好处理，其次是因为 $Min$ 是不降的，所以不会存在左端点向左移动的情况，那么 $d_{i, Min_i}$ 就一定在答案的贡献里。

所以代码如下：

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

const int N = 1e6+10;
const int inf = 0x3f3f3f3f3f3f3f3f;

struct node {
    int val, l, r;
};

node dq[2*N];

int head = 0, tail = -1;

int n;
int a[N], b[N];

int p[N];
int Min[N], Max[N];

int lazy, sum;

node pop_back() {
    node res = dq[tail--];
    sum = sum - (res.val + lazy) * (res.r - res.l + 1);
    return res;
}

node pop_front() {
    node res = dq[head++];
    sum = sum - (res.val + lazy) * (res.r - res.l + 1);
    return res;
}

void push_back(node x) {
    dq[++tail] = {x.val - lazy, x.l, x.r};
    sum += x.val * (x.r - x.l + 1);
}

bool empty() {
    return head > tail;
}

signed main() {
    cin >> n;
    for (int i = 1;i<= n;i++) {
        cin >> a[i] >> b[i];
    }
    for (int i = 1;i<= n;i++) {
        cin >> p[i];
    }

    int low = 0;
    for (int i = 1;i<= n;i++) {
        Min[i] = 0, Max[i] = i-1;
    }
    for (int i = 1;i<= n;i++) {
        if (p[i] == -1) continue;
        Max[p[i]] = min(Max[p[i]], i-1);
        Min[p[i]+1] = max(Min[p[i]+1], i);
        low = p[i];
    }
    for (int i = 2;i<= n;i++) {
        if (Min[i] < Min[i-1]) Min[i] = Min[i-1];
    }

    int ans = -inf;
    if (low == 0) ans = 0;
    int lt = 0, rt = 0, First = 0;

    for (int i = 1;i<= n;i++) {
        if (Min[i] > Max[i]) break;
        while (!empty() && dq[head].r <= Min[i]) {
            node p = pop_front();
            First += (p.val + lazy) * (p.r - p.l + 1);
        }
        while (!empty() && dq[head].l <= Min[i]) {
            First += (dq[head].val + lazy) * (Min[i] - dq[head].l + 1);
            sum -= (Min[i] - dq[head].l + 1) * (dq[head].val + lazy);
            dq[head].l = Min[i]+1;
        }
        lt = Min[i];
        if (empty()) rt = lt;

        First += a[i] + Min[i] * b[i];

        if (Max[i] < rt) {
            while (!empty() && dq[tail].l > Max[i]) pop_back();
            while (!empty() && dq[tail].r > Max[i]) {
                sum -= (dq[tail].r - Max[i]) * (dq[tail].val + lazy);
                dq[tail].r = Max[i];
            }
            rt = Max[i];
            if (empty()) lt = rt;
        } else if (rt < Max[i]) {
            push_back({0, rt+1, Max[i]});
            rt = Max[i];
        }

        if (Min[i] + 1 <= Max[i]) {
            lazy += b[i];
            sum += (rt - lt) * b[i];
            
            if (b[i] < 0) {
                int last = Max[i]+1;
                while (!empty() && dq[tail].val + lazy < 0) {
                    last = dq[tail].l, pop_back();
                }
                if (last <= Max[i]) push_back({0, last, Max[i]});
            }
        }

        if (i >= low) {
            ans = max(ans, First + sum);
        }
    }

    cout << ans << endl;
    return 0;
}