2023.8.10 nfls集训Day2 考试总结

2023暑nfls

前言：nfls 的模拟赛居然是 3h8题？采用类似 CF 的方式，每题的权值不同，很奇妙。

大概问了一下情况，一般 $A$ 到 $E$ 比较简单，和 $F,G,H$ 跨度较大。

那就不出意外每场都先做 $F,G,H$ 好了。

Result

Progress

前 $30$ min 不知道干了些啥+开题。

F：怪怪题，看不出是啥
G：感觉有点一眼，应该是线段树优化建图
H：带修最大矩形面积？难不成有动态悬线法？？？感觉很困难

先想 $H$ 看看实力，静态 $n^2$ 可以悬线法，能不能改一改变成动态。

改了很久没改出来，静态好像也没有其他 $n^2$ 写法了我记得，那看起来就不是很可做了。

此时已经快过去 1h 了，有点慌，转头看 $F$

数据范围很小，把线段拆成端点，这样可以得到每个点的取值范围。

变成一堆线段选点，但是不会保证端点能选到。

先不管，冲个二分图匹配上去，果然挂了，但是只是选不到端点。

失了智，想了很久怎么处理这个东西，后来发现倒着限制一下取值的数能选哪些点就好了。

改一改 $F$ 很快过了。

开 $G$，感觉很板，直接线段树优化建图开冲，然后就是不断修细节调代码。

可能是第一次写线段树优化建图，出了很多小问题，快下考之前惊险过掉。

剩下一点时间冲了个 $A,B,C$。

听讲题，发现 $H$ 题意看错了！怎么是正方形啊！！！正方形那不是萌萌题吗！！！

有点小寄，不过通过情况还可以，$G$ 居然是 $SNOI2017$ 的题。

F 还原排列

全排列构造方案，可以考虑二分图匹配，位置与树形成自然的二分图。

将一个区间拆成单点，对两侧的点都维护好相应的连边限制，按限制连边。

需要注意的是，一开始只搞了一侧限制，这样不能保证 极值正好取到 $v$，而你反着限制一下，就可以防止一些点明明能取端点但是乱取。

G 地雷

没啥好说的，码力题，因为连边是点连到区间，所以可以线段树优化建图。

然后跑个缩点搞成 DAG，拓扑求一下答案。

H 选择正方形

注意是 正方形！！！！！

答案显然单调，且修改只加入限制点。

很容易想到倒过来，让答案变大。

那么答案如果变大，就一定包含上一个限制点，可以以其为核心算答案。

矩形和正方形不同的就在于这个算答案的过程。

对于正方形，我们可以直接二分，做check

那就是判断在限制点周围一圈，能不能用有 $mid$ 的矩形。

由于四个方向边长一样，我们显然扫一维维护一维。

对横轴做滑动窗口，那就是判断上下能否凑够 $mid$

注意到这个上下的可行的长度显然是独立的，把两个分开做，对于每个窗口求出最大的长度。

这个过程只要先预处理一下每一列的答案，然后单调队列DP一下，十分容易。

最后把上下拼起来判断一下就好了。

有点抽象，贴个代码。

#include <bits/stdc++.h>
using namespace std;
inline int read() {
    int x = 0;
    char c = getchar();
    bool f = 0;
    while (!isdigit(c)) f |= (c == '-'), c = getchar();
    while (isdigit(c)) x = (x * 10) + (c ^ 48), c = getchar();
    return f ? -x : x;
}
const int maxn = 2005;
int n, m, K;
int A[maxn][maxn], f[maxn][maxn], Answer[maxn];
int Que[maxn], head, tail, Up[maxn][maxn], Down[maxn][maxn], FUp[maxn], FDown[maxn];
pair<int, int> Point[maxn];
inline void Solve0() {
    for (register int i = 1; i <= n; ++i)
        for (register int j = 1; j <= m; ++j) {
            if (!A[i][j])
                f[i][j] = 0;
            else
                f[i][j] = min(f[i - 1][j - 1], min(f[i - 1][j], f[i][j - 1])) + 1;
            Answer[K] = max(Answer[K], f[i][j]);
        }
    for (register int j = 1; j <= m; ++j) {
        for (register int i = 1; i <= n; ++i)
            if (!A[i][j])
                Up[i][j] = 0;
            else
                Up[i][j] = Up[i - 1][j] + 1;
        for (register int i = n; i >= 1; --i)
            if (!A[i][j])
                Down[i][j] = 0;
            else
                Down[i][j] = Down[i + 1][j] + 1;
    }
}
inline bool Check(int Id, int mid) {
    head = 1, tail = 0;
    for (register int i = Point[Id].second - mid + 1; i <= min(m, Point[Id].second + mid - 1); ++i) {
        while (head <= tail && i - Que[head] + 1 > mid) head++;
        while (head <= tail && Up[Point[Id].first][i] <= Up[Point[Id].first][Que[tail]]) tail--;
        Que[++tail] = i;
        if (i >= Point[Id].second)
            FUp[i] = Up[Point[Id].first][Que[head]];
    }
    head = 1, tail = 0;
    for (register int i = Point[Id].second - mid + 1; i <= min(m, Point[Id].second + mid - 1); ++i) {
        while (head <= tail && i - Que[head] + 1 > mid) head++;
        while (head <= tail && Down[Point[Id].first][i] <= Down[Point[Id].first][Que[tail]]) tail--;
        Que[++tail] = i;
        if (i >= Point[Id].second)
            FDown[i] = Down[Point[Id].first][Que[head]];
    }
    for (register int i = Point[Id].second; i <= min(m, Point[Id].second + mid - 1); ++i)
        if (FUp[i] + FDown[i] - 1 >= mid)
            return 1;
    return 0;
}
inline void Solve(int Id) {
    int l = Answer[Id] - 1, r = min(n, m) + 1;
    while (l + 1 < r) {
        int mid = (l + r) >> 1;
        if (Check(Id, mid))
            l = mid;
        else
            r = mid;
    }
    Answer[Id - 1] = max(l, Answer[Id]);
}
inline void Ready(int Id) {
    A[Point[Id].first][Point[Id].second] = 1;
    for (register int i = 1; i <= n; ++i)
        if (!A[i][Point[Id].second])
            Up[i][Point[Id].second] = 0;
        else
            Up[i][Point[Id].second] = Up[i - 1][Point[Id].second] + 1;
    for (register int i = n; i >= 1; --i)
        if (!A[i][Point[Id].second])
            Down[i][Point[Id].second] = 0;
        else
            Down[i][Point[Id].second] = Down[i + 1][Point[Id].second] + 1;
}
int main() {
    //  freopen("H.in", "r", stdin);
    //  freopen("H.out", "w", stdout);
    n = read(), m = read(), K = read();
    char c;
    for (register int i = 1; i <= n; ++i)
        for (register int j = 1; j <= m; ++j) {
            while (!isalpha(c = getchar()) && c != '.')
                ;
            A[i][j] = (c == '.');
        }
    for (register int i = 1; i <= K; ++i) {
        Point[i].first = read(), Point[i].second = read();
        A[Point[i].first][Point[i].second] = 0;
    }
    Solve0();
    for (register int i = K - 1; i >= 1; --i) Ready(i + 1), Solve(i + 1);
    for (register int i = 1; i <= K; ++i) printf("%d\n", Answer[i]);
    return 0;
}