Longest Subarray

解题思路

本题求一个最大的子区间，满足区间内的数字要么出现次数大于等于k次，要么没出现过。给定区间内的数字范围是1~c。

如果r为右边界，对于一种数字x，满足条件的左边界l的范围是r左边第一个x出现的位置+1(即这段区间内没有出现过x，如果x在1_{r内都没有出现过，那么1}r自然都是l的合法范围)，以及1到从右往左数数第k个x出现的位置(即这段区间内的x出现次数大于等于k)。所以我们只要找到同时是c种数字的合法左边界的位置中最小的，然后枚举所有的i作为右边界即可得出答案。

但是这样直接写肯定超时。所以我们用线段树来维护每个位置可以作为多少种数字的合法范围，以及一个区间内的最大值。在查询的时候只要尽量往左子树找就可以了。还有一个问题，难道我们要每次枚举都重新划分范围么？肯定是不行的。所以我们记录所有数字出现的位置，然后先让n为右边界，用线段树维护好其合法范围，再让右边界往左移，每次移动其实只是把旧的右边界归0，然后改变了旧的右边界上的数字的合法范围。我们已经记录了数字的出现位置，利用这个，只需要在线段树上进行几次修改即可，因为当左边界比右边界小的时候会得到负数，不会使答案更新，所以不归零也不会影响答案。

代码如下

#include <bits/stdc++.h>

#define INF 0x3f3f3f3f

using namespace std;

typedef long long ll;

inline int read(){

    int res = 0, w = 0; char ch = 0;

    while(!isdigit(ch)){

        w |= ch == '-', ch = getchar();

    }

    while(isdigit(ch)){

        res = (res << 3) + (res << 1) + (ch ^ 48);

        ch = getchar();

    }

    return w ? -res : res;

}

const int N = 100005;

struct T{

    int l, r;

    int maxx, lazy;

}tree[N<<2];

int a[N];

vector<int> vec[N];

void build(int k, int l, int r)

{

    tree[k].l = l;

    tree[k].r = r;

    tree[k].lazy = tree[k].maxx = 0;

    if(l == r)

        return;

    int mid = (l + r) / 2;

    build(2*k, l, mid);

    build(2*k+1, mid + 1, r);

}

inline void push_down(int k)

{

    if(tree[k].lazy){

        tree[2*k].maxx += tree[k].lazy;

        tree[2*k+1].maxx += tree[k].lazy;

        tree[2*k].lazy += tree[k].lazy;

        tree[2*k+1].lazy += tree[k].lazy;   //+=

        tree[k].lazy = 0;

    }

}

void insert(int k, int l, int r, int u)

{

    if(l > r)

        return;

    if(tree[k].l >= l && tree[k].r <= r){

        tree[k].lazy += u;

        tree[k].maxx += u;

        return;

    }

    int mid = (tree[k].l + tree[k].r) / 2;

    push_down(k);

    if(l <= mid)

        insert(2*k, l, r, u);

    if(r > mid)

        insert(2*k+1, l, r, u);

    tree[k].maxx = max(tree[2*k].maxx, tree[2*k+1].maxx);

}

int n, c, k;

int query(int k)

{

    if(tree[k].maxx < c)

        return n + 1;

    if(tree[k].l == tree[k].r)

        return tree[k].l;

    push_down(k);

    if(tree[2*k].maxx == c)

        return query(2*k);

    else

        return query(2*k+1);

}

int main()

{

    while(scanf("%d%d%d", &n, &c, &k) != EOF){

        for(int i = 1; i <= n; i ++)

            a[i] = read();

        for(int i = 1; i <= n; i ++)

            vec[a[i]].push_back(i);

        build(1, 1, n);

        for(int i = 1; i <= c; i ++){

            if(vec[i].empty())

                insert(1, 1, n, 1);

            else {

                insert(1, vec[i][vec[i].size() - 1] + 1, n, 1);

                if(vec[i].size() >= k)

                    insert(1, 1, vec[i][vec[i].size() - k], 1);

            }

        }

        int ans = 0;

        for(int i = n; i >= 1; i --){

            ans = max(ans, i - query(1) + 1);

            if(vec[a[i]].size() >= k)

                insert(1, 1, vec[a[i]][vec[a[i]].size() - k], -1);

            vec[a[i]].pop_back();

            if(vec[a[i]].empty())

                insert(1, 1, i, 1);

            else {

                insert(1, vec[a[i]][vec[a[i]].size() - 1] + 1, i - 1, 1);

                if(vec[a[i]].size() >= k)

                    insert(1, 1, vec[a[i]][vec[a[i]].size() - k], 1);

            }

        }

        printf("%d\n", ans);

    }

    return 0;

}

巴特西

2019杭电多校第二场hdu6602 Longest Subarray(线段树)

Longest Subarray

解题思路

代码如下

最新文章

热门文章