「AHOI2014/JSOI2014」拼图

标签：tchar   复杂度   ref   传送门   com   time   lse   计算   处理   

「AHOI2014/JSOI2014」拼图

传送门
看到 \(n \times m \le 10^5\) ，考虑根号分治。
对于 \(n 的情况，我们可以枚举最终矩形的上下边界 \(tp, bt\)，那么我们发现最终矩形一定是由所有满足从第 \(tp\) 行到第 \(bt\) 行都是白格子的矩形顺次连接，并且两端再各自接上一个最大的前缀和一个最大的后缀构成的。
这个我们可以 \(O(m)\) 地算。
总复杂度就是 \(O(n^2m)\)，也就是一个根号级别的。
对于 \(n \ge m\) 的情况，我们肯定不能还去枚举上下边界，但是此时我们可以对于每一个白色的格子，都找一个它上面的最远的一个白格子来构成一组上下边界，然后套用第一问的计算方法就好了。
预处理是 \(O(nm)\) 的，总复杂度是 \(O(nm^2)\)，还是一个根号级别的。
还有一个坑点就是再找前、后缀矩形时要避免重复使用一个矩阵，所以我们还得记录次大值。
参考代码：

#include 
#define rg register
#define file(x) freopen(x".in", "r", stdin), freopen(x".out", "w", stdout)
template  inline T max(T a, T b) { return a > b ? a : b; }
template  inline void read(T& s) {
    s = 0; int f = 0; char c = getchar();
    while ('0' > c || c > '9') f |= c == '-', c = getchar();
    while ('0' = l[i]; --j) if (S(tp, j, bt, j) != 0) break ; else ++rs;
        if (ls == lr[i]) mid += lr[i];
        else {
            if (ls > lmx.first) lmmx = lmx, lmx = (node) { ls, i };
            else if (ls > lmmx.first) lmmx = (node) { ls, i };
            if (rs > rmx.first) rmmx = rmx, rmx = (node) { rs, i };
            else if (rs > rmmx.first) rmmx = (node) { rs, i };
        }
    }
    if (lmx.second != rmx.second)
        res = max(res, (bt - tp + 1) * (lmx.first + mid + rmx.first));
    else {
        res = max(res, (bt - tp + 1) * (lmmx.first + mid + rmx.first));
        res = max(res, (bt - tp + 1) * (rmmx.first + mid + lmx.first));
    }
    return res;
}

inline void solve() {
    read(s), read(n), m = 0;
    for (rg int i = 1; i 

「AHOI2014/JSOI2014」拼图

标签：tchar   复杂度   ref   传送门   com   time   lse   计算   处理   

原文地址：https://www.cnblogs.com/zsbzsb/p/12260647.html