CF526F Pudding Monsters

记 $w_{i}$ 表示第 $i$ 行的棋子的位置在 $i$ ，那么一个大小为 $k \times k$ 的矩阵中，行的范围为 $l \to r (r - l + 1 = k)$ ，有贡献当且仅当 $max_{w} - m i n_{w} = k$ 。答案即为 $\sum_{l = 1}^{n} \sum_{r = l}^{n} [m a x_{w [l, r]} - m i n_{w [l, r]} = r - l]$ 。

记 $k = m a x - m i n - r + l$ 。考虑移动右指针 $r$ ，考察有多少个 $l$ 有贡献，将 $k$ 的变化修改在对应的 $l$ 上，那么问题转化为区间修改，查询全局有多少个 $0$ ，发现线段树等数据结构不好做。进一步发现，因为 $w_{i}$ 是一个排列，这个值不可能为负，那么 $0$ 就是最小值，线段树可以维护区间最小值和最小值的个数，那么这个问题就可以做了。

$- r$ 和 $+ l$ 很好在线段树上直接做。考虑 $m a x - m i n$ 怎么在线段树上修改。显然可以用单调栈，单调栈上 $[s t k_{t o p - 1} + 1, s t k_{t o p}]$ 的最值在 $s t k_{t o p}$ 上，那么每次将其原来的最值删去，最后统一将新的最值加上即可。

查看代码

#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long LL;
template <class Type>
void read(Type &x)
{
    char c;
    bool flag = false;
    while ((c = getchar()) < '0' || c > '9')
        c == '-' && (flag = true);
    x = c - '0';
    while ((c = getchar()) >= '0' && c <= '9')
        x = (x << 3) + (x << 1) + c - '0';
    flag && (x = ~x + 1);
}
template <class Type>
void write(Type x)
{
    x < 0 && (putchar('-'), x = ~x + 1);
    x > 9 && (write(x / 10), 0);
    putchar(x % 10 + '0');
}
const int N = 3e5 + 10;
int n, w[N];
struct Node
{
    int l, r, tag, mn, cnt;
} tr[N << 2];
void pushup (int x)
{
    tr[x].mn = min(tr[x << 1].mn, tr[x << 1 | 1].mn);
    tr[x].cnt = 0;
    tr[x << 1].mn == tr[x].mn && (tr[x].cnt += tr[x << 1].cnt);
    tr[x << 1 | 1].mn == tr[x].mn && (tr[x].cnt += tr[x << 1 | 1].cnt);
}
void add (int x, int k)
{
    tr[x].mn += k, tr[x].tag += k;
}
void pushdown (int x)
{
    add(x << 1, tr[x].tag), add(x << 1 | 1, tr[x].tag);
    tr[x].tag = 0;
}
void build (int l = 1, int r = n, int x = 1)
{
    tr[x].l = l, tr[x].r = r;
    if (l == r)
        return tr[x].mn = l, tr[x].cnt = 1, void();
    int mid = l + r >> 1;
    build(l, mid, x << 1), build(mid + 1, r, x << 1 | 1);
    pushup(x);
}
void modify (int l, int r, int k, int x = 1)
{
    if (l > r || tr[x].l > r || l > tr[x].r)
        return;
    if (tr[x].l >= l && tr[x].r <= r)
        return add(x, k);
    pushdown(x);
    modify(l, r, k, x << 1), modify(l, r, k, x << 1 | 1);
    pushup(x);
}
int top1, stk1[N], top2, stk2[N];
int main ()
{
    read(n);
    for (int i = 1, a, b; i <= n; i++)
    {
        read(a), read(b);
        w[a] = b;
    }
    build();
    LL res = 0;
    for (int i = 1; i <= n; i++)
    {
        while (top1 && w[stk1[top1]] > w[i])
            modify(stk1[top1 - 1] + 1, stk1[top1], w[stk1[top1]]), top1--;
        modify(stk1[top1] + 1, i, -w[i]);
        stk1[++top1] = i;
        while (top2 && w[stk2[top2]] < w[i])
            modify(stk2[top2 - 1] + 1, stk2[top2], -w[stk2[top2]]), top2--;
        modify(stk2[top2] + 1, i, w[i]);
        stk2[++top2] = i;
        modify(1, n, -1);
        res += tr[1].cnt;
    }
    write(res);
    return 0;
}