BZOJ 3100 - 排列 | Sengxian's Blog

BZOJ 3100 - 排列

#扫描

Published on 2016-10-20

题目地址

描述

给定一个长度为 $n(n\le {10}^6)$ 的序列 $a$ ，选取连续的一段使其为的一个排列。求 $k$ 的最大值。

分析

我们来看看一个区间是的一个排列的充分必要条件是什么：

没有重复的数
和为 $\frac{k(k + 1)} 2$

我们的思路是，找到所有为 $1$ 的位置，从这些位置向两边扩展。
我们先考虑向左边扩展：首先记录 $r_i$ 为 $a_i$ 右边第一个等于 $a_i$ 的位置，如果不存在则为 $\infty$ ，这个可以扫描一下， $O(n)$ 预处理。

接着从每个 $p_i$ 开始，向左扩展，设当前扩展到了 $j(p_{i - 1}<j\le p_i)$ ，设 $[j, p_i]$ 区间内 $a_i$ 的最大值为 $\mathrm{mx}$ ， $r_i$ 的最小值为 $\mathrm{R}$ 。则我们可以知道， $[j, R)$ 这一段区间是没有重复的数的。我们既然已经知道了最大值为 $\mathrm{mx}$ ，我们就需要验证， $[j, j + \mathrm{mx})$ 这一段区间是否正好是，根据之前的条件，只需要判断区间 $[j, j + \mathrm{mx})$ 的和是否是 $\frac {\mathrm{mx}(\mathrm{mx} + 1)}{2}$ 。

接下来将序列翻转，做一次同样的事，就是向右扩展了。
我们看看算法的正确性：设答案区间为 $[l, r]$ ， $1$ 的位置在 $p$ ，那么我们考虑最大值在什么地方，要么在 $p$ 的左边，要么在 $p$ 的右边，这都是可以被我们扩展到的，所以这个算法一定能够计算答案区间的答案，所以是正确的。

考虑一下卡内存，不预处理前缀和，每一次手动更新一下区间和即可，总的复杂度仍然是 $O(n)$ 。

代码

//  Created by Sengxian on 2016/10/20.
//  Copyright (c) 2016年 Sengxian. All rights reserved.
//  BZOJ 3100 扫描 + 卡内存
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
inline int ReadInt() {
    static int n, ch;
    n = 0, ch = getchar();
    while (!isdigit(ch)) ch = getchar();
    while (isdigit(ch)) n = n * 10 + ch - '0', ch = getchar();
    return n;
}

const int MAX_N = 1000000 + 3;
int n, a[MAX_N];
int r[MAX_N], st[MAX_N];

void process() {
    for (int i = 0; i < n; ++i) st[i] = n;
    for (int i = n - 1; i >= 0; --i) {
        r[i] = st[a[i]];
        st[a[i]] = i;
    }
}

int solve() {
    process();
    int m = 0;
    for (int i = 0; i < n; ++i) if (a[i] == 0) st[m++] = i;
    int ans = m > 0;
    ll sum = 0;
    st[m] = n;
    for (int i = 0, j, lst, mx_v, mn_r; i < m; ++i) {
        mx_v = 0, mn_r = r[st[i]];
        sum = 0, lst = st[i];
        for (j = st[i] - 1; j > (i == 0 ? -1 : st[i - 1]); --j) {
            sum += a[j];
            mn_r = min(mn_r, r[j]);
            if (a[j] <= mx_v) {
                if (lst == j + mx_v + 2) sum -= a[--lst];
            } else {
                mx_v = a[j];
                for (; lst < j + mx_v + 1 && lst < mn_r; ++lst) sum += a[lst];                
            }
            if (j + mx_v + 1 <= mn_r && sum == (ll)mx_v * (mx_v + 1) / 2)
                ans = max(ans, mx_v + 1);
        }
    }
    return ans;
}

int main() {
    n = ReadInt();
    for (int i = 0; i < n; ++i) a[i] = ReadInt() - 1;
    int ans = solve();
    reverse(a, a + n);
    printf("%d\n", max(ans, solve()));
    return 0;
}

UVa 12235 - Help Bubu UVa 10827 - Maximum sum on a torus