【题解】CF1000F One Occurrence

· · 题解

原题链接

解题思路

我们有一个询问区间 [l,r]，题目要求你找出其中只出现了一次的数。

我们单独考虑某个数 x，假设其在 [l,r] 中出现的下标最大的位置为 p。那么，x 在区间 [l,r] 只出现了一次等价于 p 存在并且相对于 p，x 上一次出现的位置 <l。

可以在每一个位置 i 维护 a_i 上一次出现的位置。在查询 [l,r] 的时候如果该区间上的最小值 <l，则一定有数只出现了一次。用线段树维护，同时记录一下最小值对应的数是什么即可。

为了保证在最靠右的 x 处记录信息，我们需要将询问按照右端点排序，离线处理。

代码实现

#include <bits/stdc++.h>
using namespace std;
int n,m,a[500005],pos[500005],ans[500005];
const int INF=0x7fffffff;
inline int read()
{
    char ch;int res=0;
    while(isspace(ch=getchar()));
    for(;isdigit(ch);res=res*10+ch-'0',ch=getchar());
    return res;
}
struct Data
{
    int val,id;
    Data(int v,int i): val(v),id(i){}
    inline bool operator <(const Data &b)const
        { return val<b.val; }
}infdata(INF,0);
struct TreeNode
{
    Data mn;
    TreeNode *lc,*rc;
    TreeNode(int x,int i): mn(x,i)
        { lc=rc=nullptr; }
}*rt;
typedef TreeNode *pNode;
inline void pushup(pNode i)
    { i->mn=min(i->lc->mn,i->rc->mn); }
void build(int l,int r,pNode &i=rt)
{
    i=new TreeNode(INF,0);
    if(l!=r)
    {
        int mid=(l+r)>>1;
        build(l,mid,i->lc),build(mid+1,r,i->rc);
    }
}
void modify(int p,Data x,pNode i=rt,int l=1,int r=n)
{
    if(l==r)    i->mn=x;
    else
    {
        int mid=(l+r)>>1;
        if(mid>=p)  modify(p,x,i->lc,l,mid);
        else    modify(p,x,i->rc,mid+1,r);
        pushup(i);
    }
}
Data query(int lq,int rq,pNode i=rt,int l=1,int r=n)
{
    if(r<lq || l>rq)    return infdata;
    if(l>=lq && r<=rq)  return i->mn;
    int mid=(l+r)>>1;
    return min(query(lq,rq,i->lc,l,mid),
               query(lq,rq,i->rc,mid+1,r));
}
struct Edge{ int to,w,nxt; }e[500005];
int cnt,head[500005];
inline void addEdge(int u,int v,int w)
    { e[++cnt]=(Edge){v,w,head[u]},head[u]=cnt; }
int main()
{
    n=read();
    for(int i=1;i<=n;i++)   a[i]=read();
    m=read();
    for(int i=1;i<=m;i++)
    {
        int l=read(),r=read();
        addEdge(r,l,i);
    }
    build(1,n);
    for(int i=1;i<=n;i++)
    {
        int x=a[i];
        if(pos[x])
            modify(pos[x],infdata),modify(i,Data(pos[x],x));
        else
            modify(i,Data(0,x));
        pos[x]=i;
        for(int j=head[i];j;j=e[j].nxt)
        {
            Data y=query(e[j].to,i);
            ans[e[j].w]=(y.val<e[j].to)?y.id:0;
        }
    }
    for(int i=1;i<=m;i++)   printf("%d\n",ans[i]);
    return 0;
}