BZOJ 3100 - 排列

Published on 2016-10-20

题目地址

描述

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

分析

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

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

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

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

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

考虑一下卡内存,不预处理前缀和,每一次手动更新一下区间和即可,总的复杂度仍然是 O(n)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;
}