题解 HDU6602 - Longest Subarray

题解 #

让我们先尝试固定右端点，然后对于每个右端点找到最长的子数组。

令 $pos_ {x，i}$ 为第 i 个 $x$ 的下标。假设当前的右端点是 $r \in [0，n)$ ，对于每个 $x \in [1，C]$ ,左端点不可能落在区间 $[pos_ {x，m-k + 1 } + 1，i]$ ，其中 $m$ 是直到 $r$ 为止 $x$ 的出现次数。这是因为如果左端点在这个区间内，则 $x$ 的出现将大于零且小于 $K$ ，不满足约束条件。我们可以在这些区间上加 1，那么最左的端点是值为 0 的最小下标。

现在让我们考虑一下当右端点移至 $r + 1$ 时区间如何变化。显而易见，只有 $a_ {r + 1}$ 的区间会改变。区间将从 $[pos_ {a_ {r + 1}，mk} + 1，pos_ {a_ {r + 1}，m-1}]$ 变为 $[pos_ {a_ {r + 1}，m- k + 1} + 1，pos_ {a_ {r + 1}，m}]$ 。请注意，在代码中，我们不必更改重叠的部分。

综上所述，我们需要一个支持区间修改和全局最小值查询的数据结构，aka 线段树。

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;
}