关于完全听不懂数据结构波特在说什么的事

· · 题解

比较简单的序列维护题。

没说在线就先离线扫描线。假设我们现在扫到了 r，我们要对每一个 l 维护出一个 p_l 表示 [l,p_l] 是 [l,r] 的一个合法子区间且 p_l 最小。

现在考虑动态维护这个 p 啊。现在我们加入了一个 w_i，上一次出现的位置为 c，那么 [c+1,i] 这些数都需要包含到 i 才合法。这个可以区间打标记。

接下来思考查询怎么实现。现在扫描到了 r，处理询问 [l,r]。我们需要找到最大的 c 满足 [c,r] 是 [l,r] 的合法子区间，答案就是 i \in [l,c], p_i-i 的最小值。

首先如果知道这个区间的话我们就可以直接使用线段树维护区间最小值，然后区间打标记解决查询的问题。现在问题来到了怎么找这个 c 上。

有很简单的 O(n \log n) 的维护方法。考虑一些接近线性的方法吧。开一个并查集，扫描线的时候维护并查集上每个结点 l 的根 c 表示 [c,r] 是 [l,r] 的合法子区间且 c 最大。

这个东西怎么维护呢？注意到在加入 w_i 的时候，记其上一次出现的位置为 c，那么就不再需要 c 这个位置了，那么就把并查集上结点 c 连向结点 c+1 即可。

那么找到这个 c 就只需要一个简单的并查集查询。问题解决了。

时间复杂度 O(n \log n)。存在 O(n \log \log n) 的做法。

int minn[8000005],tag[8000005];
inline void push_up(int now){minn[now]=min(minn[lc(now)],minn[rc(now)]);}
inline void push_down(int now,int l,int r)
{
    if(tag[now])
    {
        tag[lc(now)]=tag[rc(now)]=tag[now];
        Mm;
        minn[lc(now)]=tag[now]-mid+1,minn[rc(now)]=tag[now]-r+1;
        tag[now]=0;
    }
}
void modify(int l,int r,int now,int x,int y,int c)
{
    if(x<=l && r<=y)
    {
        tag[now]=c;
        minn[now]=c-r+1;
        return ;
    }
    push_down(now,l,r);
    Mm;
    if(x<=mid)  modify(l,mid,lc(now),x,y,c);
    if(mid<y)   modify(mid+1,r,rc(now),x,y,c);
    push_up(now);
}
int query(int l,int r,int now,int x,int y)
{
    if(x<=l && r<=y)    return minn[now];
    push_down(now,l,r);
    Mm,ret=1e9;
    if(x<=mid)  ret=min(ret,query(l,mid,lc(now),x,y));
    if(mid<y)   ret=min(ret,query(mid+1,r,rc(now),x,y));
    return ret;
}
struct unionFindSet{
    int fa[2000005];
    void makeSet(int up){for(int i=0;i<=up;++i) fa[i]=i;}
    int findSet(int x){return x==fa[x]?x:fa[x]=findSet(fa[x]);}
    int& operator [] (int x){return fa[x];}
}ufs;
#define mp make_pair
vector<pair<int,int>> qry[2000005];
int n,a[2000005],ans[2000005];
int lst[2000005];
int main(){
    n=read();
    for(int i=1;i<=n;++i)   a[i]=read();
    ufs.makeSet(n);
    int q=read();
    for(int i=1;i<=q;++i)
    {
        int l=read(),r=read();
        qry[r].push_back(mp(l,i));
    }
    for(int i=1;i<=n;++i)
    {
        modify(1,n,1,lst[a[i]]+1,i,i);
        if(lst[a[i]])   ufs[lst[a[i]]]=lst[a[i]]+1;
        lst[a[i]]=i;
        for(auto st:qry[i])
        {
            int l=st.first,r=ufs.findSet(l);
            ans[st.second]=query(1,n,1,l,r);
        }
    }
    for(int i=1;i<=q;++i)   write(ans[i]),puts("");
    return 0;
}