HDU6602-Longest Subarray(线段树+思维)

题目链接:HDU6602-Longest Subarray

题意:

给一个长度为n的序列,序列中的元素均在[1,c]之间,然后定义一个“good subarry”:要求区间内所有数字出现次数要么为0要么大于等于k,问最长的good subarry有多长。

题解:

对于固定的右端点,对于每种元素ci,我们可以知道,可行的左端点下标是两段连续的区间,其中一段为ci还没出现,一段为ci出现次数已经大于等于k次。

所以我们可以用线段树维护,对于每种元素,把它可行的区间全部加1,当右端点移动的时候,维护C种元素的可行左端点,查询的时候插叙线段树中最小的值为c的下标即可。

参考代码:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 2e5 + 5;
const int inf = 0x3f3f3f3f;
int n, c, k;
int a[MAXN], cnt[MAXN];
vector<int> vec[MAXN];
int sum[MAXN << 2], lazy[MAXN << 2];
//lazy维护区间和 sum维护区间最大值
void pushup(int rt)
{
    sum[rt] = max(sum[rt << 1] + lazy[rt << 1], sum[rt << 1 | 1] + lazy[rt << 1 | 1]);
}
void pushdown(int l, int r, int rt)
{
    if (lazy[rt] != 0)
    {
        lazy[rt << 1] += lazy[rt];
        lazy[rt << 1 | 1] += lazy[rt];
        sum[rt] += lazy[rt];
        lazy[rt] = 0;
    }
}
void build(int l, int r, int rt)
{
    sum[rt] = 0, lazy[rt] = 0;
    if (l == r)
        return;
    int mid = (l + r) >> 1;
    build(l, mid, rt << 1);
    build(mid + 1, r, rt << 1 | 1);
    pushup(rt);
}
void update(int L, int R, int val, int l, int r, int rt)
{
    if (L <= l && r <= R)
    {
        lazy[rt] += val;
        return;
    }
    pushdown(l, r, rt);
    int mid = (l + r) >> 1;
    if (L <= mid)
        update(L, R, val, l, mid, rt << 1);
    if (R > mid)
        update(L, R, val, mid + 1, r, rt << 1 | 1);
    pushup(rt);
}
int query_l(int L, int R, int l, int r, int rt)
{
    if (l == r && sum[rt] + lazy[rt] == c)
        return l;
    int mid = (l + r) >> 1;
    pushdown(l, r, rt);
    if (L <= mid && sum[rt << 1] + lazy[rt << 1] == c)
        return query_l(L, R, l, mid, rt << 1);
    if (R > mid && sum[rt << 1 | 1] + lazy[rt << 1 | 1] == c)
        return query_l(L, R, mid + 1, r, rt << 1 | 1);
    return inf;
}
int main()
{
    while (~scanf("%d%d%d", &n, &c, &k))
    {
        for (int i = 1; i <= c; i++)
            vec[i].clear(), cnt[i] = 0;
        for (int i = 1; i <= n; i++)
        {
            scanf("%d", &a[i]);
            vec[a[i]].push_back(i);
        }
        for (int i = 1; i <= c; i++)
            reverse(vec[i].begin(), vec[i].end());
        build(1, n, 1);
        for (int i = 1; i <= c; i++)
        {
            if (!(int)vec[i].size())
                update(1, n, 1, 1, n, 1);
            else if ((int)vec[i].size() >= k)
            {
                if (vec[i][0] != n)
                    update(vec[i][0] + 1, n, 1, 1, n, 1);
                update(1, vec[i][k - 1], 1, 1, n, 1);
            }
            else
            {
                if (vec[i][0] != n)
                    update(vec[i][0] + 1, n, 1, 1, n, 1);
            }
        }
        int ans = 0;
        for (int i = n; i >= 1; i--)
        {
            ans = max(ans, i - query_l(1, i, 1, n, 1) + 1);
            if ((int)vec[a[i]].size() - cnt[a[i]] >= k)
            {
                if (vec[a[i]][cnt[a[i]]] != n)
                    update(vec[a[i]][cnt[a[i]]] + 1, n, -1, 1, n, 1);
                if ((int)vec[a[i]].size() >= k)
                    update(1, vec[a[i]][k - 1 + cnt[a[i]]], -1, 1, n, 1);
            }
            else
            {
                if (vec[a[i]][cnt[a[i]]] != n)
                    update(vec[a[i]][cnt[a[i]]] + 1, n, -1, 1, n, 1);
            }
            cnt[a[i]]++;
            if ((int)vec[a[i]].size() - cnt[a[i]] >= k)
            {
                if (vec[a[i]][cnt[a[i]]] != n)
                    update(vec[a[i]][cnt[a[i]]] + 1, n, 1, 1, n, 1);
                update(1, vec[a[i]][k - 1 + cnt[a[i]]], 1, 1, n, 1);
            }
            if ((int)vec[a[i]].size() == cnt[a[i]])
                update(1, n, 1, 1, n, 1);
            else if ((int)vec[a[i]].size() - cnt[a[i]] < k)
                update(vec[a[i]][cnt[a[i]]] + 1, n, 1, 1, n, 1);
        }
        printf("%d\n", ans);
    }
    return 0;
}

发表留言

人生在世,错别字在所难免,无需纠正。