Solution for HDU6602 - Longest Subarray

Solution #

Let’s try to fix the right endpoint first and then find the longest subarray for each right endpoint.

Let $pos_{x,i}$ be the index of the $i$ -th occurrence of number $x$ . Assume the current right endpoint is $r\in[0,n)$ , for each $x\in[1,C]$ The left endpoint can’t fall in the interval $[pos_{x,m-k+1}+1,i]$ where $m$ is the occurrence of $x$ until $r$ . This is because if left endpoint in that interval, the occurrence of $x$ would be larger than zero and smaller than $K$ , which doesn’t satisfy the constrain. We could add 1 on those intervals and the leftmost endpoint is the smallest index whose value is 0.

Now let’s consider how the intervals change when the right endpoint moves to $r+1$ . It’s easy to see that only the interval for $a_{r+1}$ will change. The interval will change from $[pos_{a_{r+1},m-k}+1,pos_{a_{r+1},m-1}]$ to $[pos_{a_{r+1},m-k+1}+1,pos_{a_{r+1},m}]$ . Note that in the implementation we don’t have to change the overlapped interval.

In conclusion, we need a data structure that supports range modification and global minimum value query, a.k.a. segment tree.

Code #

#include <bits/stdc++.h>
 
#define forn(i, n) for (int i = 0; i < int(n); ++i)
#define for1(i, n) for (int i = 1; i <= int(n); ++i)
#define size(x) int(x.size())
#define pb push_back
 
using namespace std;
 
struct SegTree{
    int n;
    vector<int> t,lazy,pos;
    SegTree(int n_):n(n_),t(4*n),lazy(4*n),pos(4*n){
        build(1,0,n-1);
    }
    void pushup(int node){
        t[node]=min(t[node<<1],t[node<<1|1]);
        pos[node]=(t[node]==t[node<<1]?pos[node<<1]:pos[node<<1|1]);
    }
    void build(int node,int l,int r){
        if(l==r){
            pos[node]=l;
            return;
        }
        int mid=(l+r)>>1;
        build(node<<1,l,mid);
        build(node<<1|1,mid+1,r);
        pushup(node);
    }
    void addtag(int p,int x){
        t[p]+=x;
        lazy[p]+=x;
    }
    void spread(int p){
        if(lazy[p]){
            addtag(p<<1,lazy[p]);
            addtag(p<<1|1,lazy[p]);
            lazy[p]=0;
        }
    }
    void update(int node,int ql,int qr,int l,int r,int x){
        if(ql<=l&&qr>=r){
            addtag(node,x);
            return;
        }
        spread(node);
        int mid=(l+r)>>1;
        if(ql<=mid) update(node<<1,ql,qr,l,mid,x);
        if(qr>mid) update(node<<1|1,ql,qr,mid+1,r,x);
        pushup(node);
    }
    int query(int i){
        return t[1]==0?i-pos[1]+1:0;
    }
 
};
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,c,k;
    while(cin>>n>>c>>k){
        vector<vector<int>> pos(c+1,{-1});
        vector<int> a(n);
        for(auto& it:a) cin>>it;
        SegTree st(n);
        int ans=0;
        forn(i,n){
            auto& v=pos[a[i]];
            v.pb(i);
            int sz=size(v)-1;
            if(sz<k) st.update(1,v[sz-1]+1,i,0,n-1,1);
            else{
                st.update(1,v[sz-k]+1,v[sz-k+1],0,n-1,-1);
                st.update(1,v[sz-1]+1,i,0,n-1,1);
            }
            ans=max(ans,st.query(i));
        }
        cout<<ans<<endl;
    }
    return 0;
}