「Codeforces 526F」Pudding Monsters – 题解

主要思路

这个题转换一下就是：给你一个排列，然后算有多少个区间使得区间内的数可以构成一个连续的数列。

可以考虑用单调栈维护后缀最大值和后缀最小值。我们思考一下具体的约束，其实就是 \(\max – \min + 1 = len\)。所以，我们可以枚举右端点 \(i\)，然后维护单调栈的同时，使用线段树对部分区间加上 \(\max\)、减去 \(\min\) 并加上 \(1\)。那么如何判断那些位置是合法的呢？我们可以对这个等式进行移项：

\[ \max – \min – len = -1 \]

首先，当 \(l = r\) 时，这个 \(\max – \min – len = -1\)，且当 \(l < r\) 时，\(\max – \min – len \geq -1\)。所以，我们对线段树维护值为全局最小值的位置个数即可。

代码

// CF526F.cpp
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int MAX_N = 3e5 + 200;

int n, pi[MAX_N], nodes[MAX_N << 2][2], tags[MAX_N << 2], stmax[MAX_N], stmin[MAX_N], t1, t2;
ll ans;

#define lson (p << 1)
#define rson ((p << 1) | 1)
#define mid ((l + r) >> 1)

void build(int l, int r, int p)
{
    nodes[p][1] = r - l + 1;
    if (l == r)
        return;
    build(l, mid, lson), build(mid + 1, r, rson);
}

void modify(int p, int x) { nodes[p][0] += x, tags[p] += x; }

void update(int ql, int qr, int l, int r, int p, int val)
{
    if (ql <= l && r <= qr)
        return (void)(modify(p, val));
    if (tags[p])
        modify(lson, tags[p]), modify(rson, tags[p]), tags[p] = 0;
    if (ql <= mid)
        update(ql, qr, l, mid, lson, val);
    if (mid < qr)
        update(ql, qr, mid + 1, r, rson, val);
    nodes[p][0] = min(nodes[lson][0], nodes[rson][0]);
    nodes[p][1] = (nodes[lson][0] == nodes[p][0] ? nodes[lson][1] : 0) + (nodes[rson][0] == nodes[p][0] ? nodes[rson][1] : 0);
}

#undef mid
#undef rson
#undef lson

int main()
{
    scanf("%d", &n);
    for (int i = 1, x, y; i <= n; i++)
        scanf("%d%d", &x, &y), pi[x] = y;
    build(1, n, 1);
    for (int i = 1; i <= n; i++)
    {
        while (t1 > 0 && pi[stmax[t1]] < pi[i])
            update(stmax[t1 - 1] + 1, stmax[t1], 1, n, 1, -pi[stmax[t1]]), t1--;
        while (t2 > 0 && pi[stmin[t2]] > pi[i])
            update(stmin[t2 - 1] + 1, stmin[t2], 1, n, 1, pi[stmin[t2]]), t2--;
        update(1, i, 1, n, 1, -1), stmax[++t1] = stmin[++t2] = i;
        update(stmax[t1 - 1] + 1, stmax[t1], 1, n, 1, pi[i]);
        update(stmin[t2 - 1] + 1, stmin[t2], 1, n, 1, -pi[i]);
        ans += nodes[1][1];
    }
    printf("%lld\n", ans);
    return 0;
}