Visits: 288

CF526F Pudding Monsters

题意

• 给定一个 $n \times n$ 的棋盘，其中有 $n$ 个棋子，每行每列恰好有一个棋子。
• 求有多少个 $k \times k$ 的子棋盘中恰好有 $k$ 个棋子。
• $n \le 3 \times 10^5$。

题解

将二维问题转化为一维问题，即构造一个序列 $a_{1\dots n}$，对于一个点 $(x,y)$，$a_x = y$。

则原问题转化为经典的连续段计数问题。

本题没有重复元素，那也就是统计 $\max – \min + 1 = \operatorname{len}$ 的区间个数。

将右端点向右扫，用单调栈维护当前每个后缀的 $\max$ 和 $\min$，然后用线段树维护当前每个后缀的 $\max – \min – \operatorname{len}$ 的值，以及每个后缀区间的值的最小值以及最小值的个数。

显然 $\max – \min – \operatorname{len} \ge -1$，同时对于每个右端点 $r$，至少会有一个后缀的值为 $-1$（$l = r$ 时），因此每个右端点对答案的贡献都是当前后缀区间的值的最小值的个数。

时间复杂度 $\mathcal O(n \log n)$。

下面的代码其实可以处理有重复元素的情况，这时候我们需要统计的就是 $\max – \min + 1 = \operatorname{cnt}$ 的区间个数，其中 $\operatorname{cnt}$ 为区间中不同的数的个数，那么记录一下每个数上一次出现的位置即可。

代码

const int N = 3e5 + 7;
int n, a[N], sx[N], tx, sn[N], tn;
map <int, int> p;
struct T {
    int l, r, x, c, z;
} t[N<<2];
ll ans;

void build(int p, int l, int r) {
    t[p].l = l, t[p].r = r, t[p].c = r - l + 1;
    if (l == r) return;
    build(ls, l, md), build(rs, md + 1, r);
}

inline void add(int p, int x) {
    t[p].x += x, t[p].z += x;
}

void upd(int p, int l, int r, int x) {
    if (t[p].l >= l && t[p].r <= r) return add(p, x);
    if (t[p].z) add(ls, t[p].z), add(rs, t[p].z), t[p].z = 0;
    if (l <= md) upd(ls, l, r, x);
    if (r > md) upd(rs, l, r, x);
    t[p].x = min(t[ls].x, t[rs].x);
    t[p].c = (t[ls].x == t[p].x ? t[ls].c : 0) + (t[rs].x == t[p].x ? t[rs].c : 0);
}

int main() {
    rd(n);
    for (int i = 1, x, y; i <= n; i++) rd(x), rd(y), a[x] = y;
    build(1, 1, n);
    for (int i = 1; i <= n; i++) {
        while (tx && a[sx[tx]] < a[i]) upd(1, sx[tx-1] + 1, sx[tx], -a[sx[tx]]), --tx;
        while (tn && a[sn[tn]] > a[i]) upd(1, sn[tn-1] + 1, sn[tn], a[sn[tn]]), --tn;
        upd(1, p[a[i]] + 1, i, -1), p[a[i]] = sx[++tx] = sn[++tn] = i;
        upd(1, sx[tx-1] + 1, i, a[i]), upd(1, sn[tn-1] + 1, i, -a[i]);
        ans += t[1].c;
    }
    print(ans);
    return 0;
}