题解 CF526F 【Pudding Monsters】
龙之吻—水货
2019-03-11 14:36:01
# CF526F Pudding Monsters
## 题目大意
有一个大小为 $n \times n$的网格,每一行每一列都有且仅有一只
$Pudding Monster$,求这个网格有多少个正方形子网格使得这个子网格的每一行每一列都有且仅有一只$Pudding Monster$。
## 解题报告
历史遗留问题终于在今天彻底解决了 QwQ
发现这是一个二维的问题,并不好做,我们尝试把它转化为一个一维的问题。
我们把所有的$Pudding Monster$按照$x$坐标排序,记此时$y$坐标形成数组为$a$,问题就转化为了 :
给出一个排列,求这个排列有多少个区间的值是连续的,也就是求满足一下条件的区间的个数 :
区间最大值 - 区间最小值 = 区间长度 - 1
$n^2$的做法很显然,这里就不说了。
网上有许多分治的做法,但是我并不会,这里也不说了。 QwQ
这里说一种线段树的做法。
要求的是一下区间的个数 :
$\max_{l,r} - \min_{l,r} = r - l$
也就是求 :
$(\max_{l,r} - \min_{l,r}) - (r - l) = 0$
考虑在线段树上维护$(\max_{l,r} - \min_{l,r}) - (r - l)$这个值的最小值以及最小值的个数,那样我们查询只需要访问根的情况就可以了。
但是发现如果$l,r$都不确定的话这个值很难维护,所以我们选择对$r$作扫描线,每次求出以$r$结尾的合法区间的和,全部加起来就可以了。
发现这样子相比起来就容易多了。
具体如何操作呢?
首先,确定一下线段树节点上维护值的意义,设当前扫到了$r$, 当前线段树节点表示的区间为$[left, right]$,维护一个$min$,表示在当前$r$的情况下,对于所有的 $l \in [left, right]$,$(\max_{l,r} - \min_{l,r}) - (r - l)$的最小值以及最小值的个数 (如果$l > r$则暂时忽略)。发现这样可以很轻松的$update$与$pushdown$。
其次,在初始化的时候,显然表示区间$[left, right]$的最小值为$left$,最小值个数为$1$。
然后,考虑每次将$r$变为$r + 1$的时候如何修改,关于$r$的影响,只需要全局减$1$即可,对于$\max_{l,r}$和$\min_{l,r}$的影响,我们可以使用单调栈来维护(具体详见代码)。
最后,统计答案,显然。 QwQ
附上代码
```cpp
#include<cstdio>
#include<algorithm>
class SegmentTree{
private :
typedef long long ll;
struct Node{
Node *child[2];
int min, push;
ll cnt; //cnt表示合法的值, val表示 max - min + l
Node() :
min(0), push(0), cnt(0) {
child[0] = child[1] = NULL;
}
};
Node *root;
int n;
void update(Node *now) {
now->cnt = 0;
now->min = std :: min(now->child[0]->min, now->child[1]->min);
if (now->min == now->child[0]->min) {
now->cnt += now->child[0]->cnt;
}
if (now->min == now->child[1]->min) {
now->cnt += now->child[1]->cnt;
}
//now->val = now->child[0]->val + now->child[1]->val;
}
void pushDown(Node *now) {
if (now->push) {
for (register int i = 0; i < 2; i++) {
now->child[i]->min += now->push;
now->child[i]->push += now->push;
}
now->push = 0;
}
}
void buildTree(Node *now, int left, int right) {
now->min = left;
now->cnt = 1;
if (left == right) {
return;
}
int mid = (left + right) >> 1;
buildTree(now->child[0] = new Node(), left, mid);
buildTree(now->child[1] = new Node(), mid + 1, right);
update(now);
}
void addVal(Node *now, int left, int right, int l, int r, int val) {
if (left >= l && right <= r) {
now->push += val;
now->min += val;
return;
}
pushDown(now);
int mid = (left + right) >> 1;
if (r <= mid) {
addVal(now->child[0], left, mid, l, r, val);
} else if (l > mid) {
addVal(now->child[1], mid + 1, right, l, r, val);
} else {
addVal(now->child[0], left, mid, l, r, val);
addVal(now->child[1], mid + 1, right, l, r, val);
}
update(now);
}
public :
void init(int x) {
buildTree(root = new Node(), 1, n = x);
}
void addVal(int l, int r, int val) {
addVal(root, 1, n, l, r, val);
}
ll query() {
return root->cnt;
}
};
class Solution{
private :
static const int maxn = 3e5 + 7;
struct Node{
int x, y;
Node(int x = 0, int y = 0) :
x(x), y(y) {}
bool operator < (const Node &x) const {
return this->x < x.x;
}
};
int n, a[maxn], max[maxn], min[maxn], cntMax, cntMin;
long long ans;
Node p[maxn];
SegmentTree tree;
public :
Solution() {
Get();
Solve();
}
void Get() {
scanf("%d", &n);
for (register int i = 1; i <= n; i++) {
scanf("%d %d", &p[i].x, &p[i].y);
}
}
void Solve() {
std::sort(p + 1, p + 1 + n);
for (register int i = 1; i <= n; i++) {
a[i] = p[i].y;
//printf("%d ", a[i]);
}
//putchar('\n');
//++n;//, a[n] = n;
tree.init(n);
/*
for (register int i = 1; i <= n; i++) {
printf("%d ", a[i]);
}
putchar('\n');
*/
for (register int i = 1; i <= n; i++) {
// do somthing
tree.addVal(1, n, -1);
for (; cntMax && a[i] > a[max[cntMax]]; cntMax--) {
// do something
tree.addVal(max[cntMax - 1] + 1, max[cntMax], a[i] - a[max[cntMax]]);
}
max[++cntMax] = i;
for (;cntMin && a[i] < a[min[cntMin]]; cntMin--) {
// do something
tree.addVal(min[cntMin - 1] + 1, min[cntMin], a[min[cntMin]] - a[i]);
}
min[++cntMin] = i;
ans += tree.query();
//printf("%d : %lld\n", i, tree.query());
}
printf("%lld\n", ans);
}
};
Solution sol;
int main() {}
```