CF1000F One Occurrence 题解

· · 题解

\mathcal{Preface}

我今天一整个晚上使用了主席树，想了很多种实现方式，但是怎么做都有点问题，最终从以前做过的 P1972 [SDOI2009] HH的项链 找到了思路，其实这两道题实现方式挺像的，可以说双倍经验。

\mathcal{Solution}

这是一篇主席树的题解。

题目要求我们输出一个区间 [l,r] 内任意一个出现次数有且仅有一次的数。

考虑如何暴力实现。

观察数据范围，可以发现数的范围不大，完全可以开下一个值域的数组。于是我们可以对于每个询问，暴力枚举每一个数，并统计出现次数。统计完成后再次枚举一遍，如果某个数出现的次数为 1，则输出即可。

然而时间复杂度为 \mathcal{O(nq)}，考虑优化。

思考暴力的本质，即我们如果发现区间 [l,r] 内一个数出现的次数大于 1，那么一定不合法。所以我们只需要记录一个数 x 之前出现的位置 lst_x 即可。如果 lst_x \ge l，即此区间内 x 的出现次数至少为 2，那么我们的答案就一定不会为 x。

一个显而易见的思路是，我们维护一个建立在数组下标上的主席树，每个节点维护此节点范围内所有数中最小的 lst_x 及其对应的 x。然而，直接这样做并不能保证正确性。一个区间 [l,r] 中，数 x 可能出现多次，区间内第一个 x 所对应的 lst_x 自然小于 l，但是如果我们在主席树的 pushup 操作中更新父节点的是这个第一个 x，那么最后查询的时候就会出错。

如何解决这个问题？再次仔细思考，发现每次出现一个新的 x 的时候，将 lst_x 位置的 lst_{x^{'}} 修改为 INF 即可。这样做的话，我们一定不会访问到之前的一个 x，使得其 lst_x 小于区间左端点了。即，如果我们需要判断答案是否可以为 x，则一定会访问最新的出现 x 的位置。

然后查询的时候，返回此区间内 lst_x 最小值，如果小于区间左端点则输出对应的 x，否则输出 0 即可。

时间复杂度 \mathcal{O(n\log n + q \log n)}。
将序列最大值看作与 n 同阶，则空间复杂度 \mathcal{O(n\log n)}。

\mathcal{Code}

如有细节问题不会实现，可以参考下面的代码，自认为写得比较好看。

#include<bits/stdc++.h>
#define PII pair<int,int>
#define F first
#define S second
using namespace std;
typedef long long LL;
const int N=5e5+5,M=41 ,INF=1e9,MX=5e5;

int n,Q;
int a[N];

struct qwq{
    int ls,rs;
    int mn,wh; 
    // mn 为此主席树节点包含所有下标最小的 lst_x，wh 为其对应的 x。 
    qwq(){
        ls=rs=0;
        mn=INF; wh=0;
        // mn 初始需要设置为正无穷。 
    }
}t[N*M];
int rt[N],cnt;

qwq pushup(qwq c,qwq a,qwq b){
    if(a.mn < b.mn){
        c.mn=a.mn;
        c.wh=a.wh;      
    }
    else{
        c.mn=b.mn;
        c.wh=b.wh;          
    }
    return c;
}

void Insert(int p,int &q,int l,int r,int x,int val){
    q=++cnt;
    t[q]=t[p];
    if(l==r){
        t[q].mn=val;
        t[q].wh=a[x];
        return;
    }
    int mid=(l+r)>>1;
    if(x<=mid) Insert(t[p].ls,t[q].ls,l,mid,x,val);
    else Insert(t[p].rs,t[q].rs,mid+1,r,x,val);
    t[q]=pushup(t[q],t[t[q].ls],t[t[q].rs]);
}

qwq query(int p,int l,int r,int x,int y){
    if(l>=x && r<=y) return t[p];
    int mid=(l+r)>>1;
    if(y<=mid) return query(t[p].ls,l,mid,x,y);
    else if(x>mid) return query(t[p].rs,mid+1,r,x,y);
    else return pushup(t[p],query(t[p].ls,l,mid,x,y),query(t[p].rs,mid+1,r,x,y));
}

int lst[N];

int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        if(lst[a[i]]){
            Insert(rt[i-1],rt[i],1,MX,lst[a[i]],INF);
            Insert(rt[i],rt[i],1,MX,i,lst[a[i]]);
        }
        else Insert(rt[i-1],rt[i],1,MX,i,0);
        lst[a[i]]=i;
    }

    scanf("%d",&Q);
    int l,r;
    while(Q--){
        scanf("%d%d",&l,&r);
        qwq ans=query(rt[r],1,MX,l,r);
        if(ans.mn<l) printf("%d\n",ans.wh);
        else printf("0\n"); 
    }
    return 0;
}