国庆集训 Test 2

国庆集训 Test 2

T1

对于最多拆分次数，大概考虑下每次拆数折个 1 出来，那么当 $n\leq 2$ 时即为 0，否则为 $n-2$。

对于最少拆分次数，我们暴力 dp 转移打表发现，答案一定是 $\lfloor\frac{w}{2}\rfloor$。

然而考场挂成 70 pts，原因是最多拆分次数没有判掉 $1$，直接输出的 $n- 2 \times m$。

T2

发现是正方形，我们手膜一下样例会简单发现规律：一定是先把正方形边角等分填好，然后再填内部。我们第$i$ 次填时大概是边长为 $2^i + 1$ 的正方形，然后增大一圈。

实现上我们需要实数高精。（？？？）

T3

首先，我们发现对于 $\text{O}(n^2)$ 时间复杂度的暴力做法是悬线法，预处理出以 $h_i$ 为高度，最左能拓展到的位置 $pre_i$，以及最右能拓展到的位置 $nxt_i$。令 $s_i$ 表示前 $i$ 所构成的最大子矩形的面积，那么 dp 转移方程为

$\max \{ ( \min \{ nxt_i , j \} - pre_i + 1 ) \times h_i \}$

那么我们考虑单调上升的部分分，那么显然有 dp 转移方程为

$\max \{ (i-j) \times h_j \}$

使用斜率优化维护凸包可以拿到 70 pt。

std 使用了李超树维护，（其实看着就有点板），大概讲的就是在线段树查询时需要二分查找，时间复杂度为 $\text{O}(n\cdot{ \log{n} }^2)$，详细的之后专门写一篇笔记。

此时却可以有一个时间复杂度更优的做法。我们发现此题的询问具有单调性，那么意味着我们可以在线段树上对于每一个结点维护一个凸包。那么每次插入一个点时仅会对 $\log{n}$ 个结点产生影响（注意到使用了标记永久化的思想）；每次询问也仅会对 $\log{n}$ 个结点进行查询。那么对于每个结点需要开 vector 储存。时间复杂度为 $\text{O}(n \log{n})$，空间开销也是同级别的（这里比李超树要劣一点）。

#include <iostream>
#include <cstdio>
#include <cctype>
#include <vector>
using namespace std;

template <typename T>
inline T read() {
    T x = 0, f = 1; char c = getchar();
    while (! isdigit(c)) {if (c == '-') f = - f; c = getchar(); }
    while (isdigit(c)) x = x * 10 + (c ^ 48), c = getchar();
    return x * f;
}

#define lint long long int
#define ulint unsigned lint
#define readint read<int>()
#define readlint read<lint>()
const int inf = 1e9 + 1e7, MAXN = 2e5 + 1e1;
const lint INF = 1e18 + 1e9;

struct Node {
    int l, r, h, t;
    vector <int> q;
} ;
int pre[MAXN], nxt[MAXN], n;
lint h[MAXN], maxn;
vector <int> G[MAXN];

double Slope(int x0, int x1) {
    return 1.0 * ((pre[x0] - 1) * h[x0] - (pre[x1] - 1) * h[x1]) / (h[x0] - h[x1]) ;
}

struct SegmentTree {
    Node tree[MAXN << 2];

    void Build(int l, int r, int x) {
        tree[x].l = l, tree[x].r = r;
        if (l == r) ;
        else {
            int mid = l + r >> 1;
            Build(l, mid, x << 1), Build(mid + 1, r, x << 1 | 1);
        }
        return ;
    }

    void Update(int ql, int qr, int k, int x) {
        int l = tree[x].l, r = tree[x].r;
        if (qr < l || r < ql) return ;
        if (ql <= l && r <= qr) {
            while (tree[x].h < tree[x].t && h[tree[x].q[tree[x].t - 1]] == h[k]) -- tree[x].t;
            while (tree[x].h < tree[x].t - 1 && Slope(tree[x].q[tree[x].t - 2], tree[x].q[tree[x].t - 1]) > Slope(tree[x].q[tree[x].t - 2], k)) -- tree[x].t;
            if (tree[x].t < tree[x].q.size()) tree[x].q[tree[x].t ++] = k;
            else tree[x].q.push_back(k), tree[x].t ++;
        }
        else Update(ql, qr, k, x << 1), Update(ql, qr, k, x << 1 | 1);
        return ;
    }

    lint Query(int ql, int qr, int k, int x) {
        int l = tree[x].l, r = tree[x].r;
        if (qr < l || r < ql) return 0;
        lint res = 0;
        while (tree[x].h < tree[x].t - 1 && Slope(tree[x].q[tree[x].h], tree[x].q[tree[x].h + 1]) <= 1.0 * k) ++ tree[x].h;
        if (tree[x].h < tree[x].t) res = (k - pre[tree[x].q[tree[x].h]] + 1) * h[tree[x].q[tree[x].h]];
        if (ql <= l && r <= qr) ;
        else{
            res = max(Query(ql, qr, k, x << 1), res);
            res = max(Query(ql, qr, k, x << 1 | 1), res);
        }
        return res;
    }
} st;

int main(void) {

    scanf("%d", &n);
    for (int i = 1; i <= n; i ++) h[i] = readint;
    for (int i = 1; i <= n; i ++) pre[i] = nxt[i] = i;
    for (int i = 1; i <= n; i ++)
        for (; i > 1 && h[pre[i] - 1] >= h[i]; pre[i] = pre[pre[i] - 1]) ;
    for (int i = n; i; i --)
        for (; i < n && h[nxt[i] + 1] >= h[i]; nxt[i] = nxt[nxt[i] + 1]) ;
    for (int i = 1; i <= n; i ++) G[nxt[i]].push_back(i);
    st.Build(1, n, 1);
    for (int i = 1; i <= n; i ++) {
        for (int j = 0; j < G[i].size(); j ++) 
            maxn = max((i - pre[G[i][j]] + 1) * h[G[i][j]], maxn);
        st.Update(i, nxt[i], i, 1);
        maxn = max(st.Query(i, i, i, 1), maxn);
        printf("%lld ", maxn);
    }
    puts("");

    return 0;
}