CF1000F One Occurrence 题解

Problem Link | CodeForces Link

一发线段树的做法。

Solution

最初的想法是维护每个元素上次出现的下标 $last$ 数组，以样例 1 1 2 3 2 4 为例，维护出来的结果即为 0 1 0 0 3 0，答案就是查找区间 $[l,r]$ 内是否有 $last_i<l$ 的元素。

但这样会出现一个问题：当区间内有元素出现了多次，统计结果会变得不正确。以样例第二组询问为例，$a_1=a_2=1$，而 $last_1=0<1$，看上去可行但实际则出现了两个 $1$。

一个可行的解决措施是只保留每个数最后一次出现的 $last$ 值，而将前面的值作废。经过这样的操作，样例处理结果即为（下标从 $1$ 开始）：

$$\begin{aligned} a=&\{1,&1,&2,&3,&2,&4\}\\ last=&\{\text{INF},&1,&\text{INF},&0,&3,&0\} \end{aligned}$$

由于在维护靠后的 $last$ 时会对前面已经维护的 $last$ 造成影响，故我们需要将询问离线，并按区间右端点排序。保证处理当前询问 $[l,r]$ 区间时 $last_r$ 没有被作废。

则程序为单点修改 $last$ 区间查询 $last$ 的最值。值得注意的是维护线段时应保存区间 $last$ 的最小值和该值的下标。区间最小值是为了判断最小的 $last$ 是否在区间内，不是则证明区间内有最小值。最小值下标是为了输出结果。

相比其他做法码量稍大，但维护 $last$ 的 trick 还是有些用处的。

Core Code

const int N=5e5+10;
int n,m;
int a[N];
int last[N];
int t[N];
int ans[N];
struct qs
{
    int l,r,id;
}q[N];
int cmp(qs x,qs y)
{
    return x.r<y.r;
}
struct tree
{
    int val,pos;
};
struct node
{
    int val[N*4],pos[N*4],siz[N*4];
    void pushup(int p)
    {
        if(val[p*2]<val[p*2+1]) val[p]=val[p*2],pos[p]=pos[p*2];
        else val[p]=val[p*2+1],pos[p]=pos[p*2+1];
    }
    void build(int p,int l,int r)
    {
        if(l==r)
        {
            val[p]=INF;
            pos[p]=l;
            return ;
        }
        int mid=(l+r)>>1;
        build(p*2,l,mid);
        build(p*2+1,mid+1,r);
        pushup(p);
    }
    void modify(int p,int l,int r,int x,int w)
    {
        if(l==r)
        {
            val[p]=w;
            return ;
        }
        int mid=(l+r)>>1;
        if(x<=mid) modify(p*2,l,mid,x,w);
        else modify(p*2+1,mid+1,r,x,w);
        pushup(p);
    }
    tree query(int p,int l,int r,int x,int y)
    {
        if(x<=l && r<=y)
        {
            return {val[p],pos[p]};
        }
        int mid=(l+r)>>1;
        tree res={INF,0};
        if(x<=mid)
        {
            tree tmp=query(p*2,l,mid,x,y);
            if(tmp.val<res.val)
            {
                res.val=tmp.val;
                res.pos=tmp.pos;
            }
        }
        if(y>=mid+1)
        {
            tree tmp=query(p*2+1,mid+1,r,x,y);
            if(tmp.val<res.val)
            {
                res.val=tmp.val;
                res.pos=tmp.pos;
            }
        }
        return res;
    }
}g;
int main()
{
    n=read();
    for(int i=1;i<=n;i++)
    {
        a[i]=read();
        last[i]=t[a[i]];
        t[a[i]]=i;
    }
    m=read();
    for(int i=1;i<=m;i++)
    {
        q[i].l=read();q[i].r=read();q[i].id=i;
    }
    sort(q+1,q+m+1,cmp);
    g.build(1,1,n);
    int j=1;
    for(int i=1;i<=n;i++)
    {
        g.modify(1,1,n,i,last[i]);
        if(last[i]!=0) g.modify(1,1,n,last[i],INF);
        while(q[j].r==i && j<=m)
        {
            tree res=g.query(1,1,n,q[j].l,q[j].r);
            if(res.val<q[j].l) ans[q[j].id]=a[res.pos];
            else ans[q[j].id]=0;
            j++;
        }
    }
    for(int i=1;i<=m;i++)
    {
        cout<<ans[i]<<endl;
    }
    return 0;
}