HDU 6602 Longest Subarray

Description:

You are given two integers $C,K$ and an array of $N$ integers $a_1, a_2, ..., a_N$ . It is guaranteed that the value of $a_i$ is between $1$ to $C$ .

$$\begin{equation*} \forall x \in [1, C], \; \sum\limits_{i = l}^r[a_i = x] = 0 \; or \; \sum\limits_{i = l}^r[a_i = x] \geq K \end{equation*}$$

It implies that if a number appears in the subarray, it will appear no less than $K$ times.

You should find the longest good subarray and output its length. Or you should print $0$ if you cannot find any.

Input:

There are multiple test cases.

Each case starts with $a$ line containing three positive integers $N,C,K(N,C,K \leq 10^5)$ .

The second line contains $N$ integer $a_1, a_2, ..., a_N(1 \leq a_i \leq C)$ .

We guarantee that the sum of $N$s, the sum of $C$s and the sum of $K$s in all test cases are all no larger than $5 \times 10^5$ .

Output:

For each test case, output one line containing an integer denoting the length of the longest good subarray.

Sample Input:

7 4 2
2 1 4 1 4 3 2

Sample Output:

4

题目链接

寻找一个最长连续子数列使在子数列中出现的各个数字出现次数大于等于 $k$

首先枚举右端点,对于每个右端点我们的任务是找到最远的左端点,考虑用线段树维护当前区间各个位置做左端点的对 $C$ 个数字的满足数量

每次在右端点 $r$ 位置加入一个数字 $x$

  1. 区间 $[r,r]$ 的满足数量为 $C-1$ ,这个区间只有 $x$ 不满足条件
  2. $r$ 左边第 $1$ 个 $x$ 的位置为 $pos$ ,区间 $[pos+1,r-1]$ 之间的满足数量在之前的基础上 $-1$ ,因为这些位置做左端点已经不能满足 $x$ 数字的条件,之前这些位置按照 $x$ 出现 $0$ 次进行计算,现在按照出现 $1$ 次计算
  3. $r$ 左边第 $k$ 个 $x$ 的位置为 $pos$ ,$r$ 左边第 $k-1$ 个 $x$ 的位置为 $pos'$,将区间 $[pos+1,pos']$ 的满足数量在之前的基础上 $+1$ ,因为这些位置做左端点已经可以满足 $x$ 数字的条件

AC代码:

#include <bits/stdc++.h>
const int maxn = 1e5 + 5;
struct SegTree {
    int n;
    int max[maxn * 4], lazy[maxn * 4], pos[maxn * 4];
    void Pull(int o) {
        max[o] = std::max(max[o * 2], max[o * 2 + 1]);
        pos[o] = max[o * 2] >= max[o * 2 + 1] ? pos[o * 2] : pos[o * 2 + 1];
    }
    void Push(int o) {
        if (lazy[o] != 0) {
            max[o * 2] += lazy[o];
            max[o * 2 + 1] += lazy[o];
            lazy[o * 2] += lazy[o];
            lazy[o * 2 + 1] += lazy[o];
            lazy[o] = 0;
        }
    }
    void Build(int o, int l, int r) {
        max[o] = lazy[o] = 0; pos[o] = l;
        if (l == r) return;
        int m = (l + r) / 2;
        Build(o * 2, l, m);
        Build(o * 2 + 1, m + 1, r);
        Pull(o);
    }
    void Init(int _n) {
        n = _n;
        Build(1, 1, n);
    }
    void Modify(int o, int l, int r, int ll, int rr, int v) {
        if (ll <= l && rr >= r) {
            max[o] += v;
            lazy[o] += v;
            return;
        }
        Push(o);
        int m = (l + r) / 2;
        if (ll <= m) Modify(o * 2, l, m, ll, rr, v);
        if (rr > m) Modify(o * 2 + 1, m + 1, r, ll, rr, v);
        Pull(o);
    }
    void Modify(int ll, int rr, int v) {
        Modify(1, 1, n, ll, rr, v);
    }
    int Query(int o, int l, int r, int ll, int rr, int v) {
        if (ll <= l && rr >= r) {
            if (max[o] == v) return pos[o];
            else return rr + 1;
        }
        Push(o);
        int m = (l + r) / 2;
        if (max[o * 2] == v) return pos[o * 2];
        else if (max[o * 2 + 1] == v) return pos[o * 2 + 1];
        else return rr + 1;
        Push(o);
    }
    int Query(int ll, int rr, int v) {
        return Query(1, 1, n, ll, rr, v);
    }
};
SegTree T;
std::vector<int> pos[maxn];
int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int n, c, k;
    while (std::cin >> n >> c >> k) {
        for (int i = 1; i <= c; ++i) {
            pos[i].clear();
            pos[i].push_back(0);
        }
        T.Init(n);
        int ans = 0;
        for (int r = 1, x; r <= n; ++r) {
            std::cin >> x;
            T.Modify(r, r, c - 1);
            if (pos[x].back() + 1 <= r - 1) T.Modify(pos[x].back() + 1, r - 1, -1);
            pos[x].push_back(r);
            if (pos[x].size() > k) {
                int idx = pos[x].size() - k - 1;
                T.Modify(pos[x][idx] + 1, pos[x][idx + 1], 1);
            }
            ans = std::max(ans, r - T.Query(1, r, c) + 1);
        }
        std::cout << ans << '\n';
    }
    return 0;
}
Last modification:August 26th, 2019 at 05:29 pm
如果觉得我的文章对你有用,请随意赞赏

Leave a Comment