题目链接

大意：给你一个数组，询问一个区间仅出现一次的数。

思路：我们记录每个位置x左边的第一个相同数的位置y，记为这个x的值为y，如果左边没数的话就是0，然后询问的区间必然是满足存在一个 t , t ∈ [ l , r ] t,t\in[l,r] t,t∈[l,r]，且 f ( t ) &lt; l f(t)&lt;l f(t)<l， f ( t ) f(t) f(t)就是左边第一个数的位置，如果找到的这个t，那么答案就存在。
我们将询问离线，按r升序排列，用指针扫来单点更新线段树，如果左边有相同的数的话，要把左边也重新更新一下。查询显然就是查线段树区间最小值。
用两个数组储存最小值和下标即可实现上述操作

细节见代码：

#include<bits/stdc++.h>

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define LL long long
#define pii pair<int,int>
#define SZ(x) (int)x.size()
#define all(x) x.begin(),x.end()

using namespace std;

LL gcd(LL a, LL b) {return b ? gcd(b, a % b) : a;}
LL lcm(LL a, LL b) {return a / gcd(a, b) * b;}
LL powmod(LL a, LL b, LL MOD) {LL ans = 1; while (b) {if (b % 2)ans = ans * a % MOD; a = a * a % MOD; b /= 2;} return ans;}
const int N = 5e5 + 3;
const LL mod = 1e9 + 7;
struct uzi{
    int l,r,i;
    bool operator <(const uzi & t)const{
        return r<t.r;
    }
}p[N];
int n,m,a[N],t[N<<2];
#define mid (l+r>>1)
#define ls o<<1
#define rs o<<1|1
int nex[N<<2];
void build(int o,int l,int r){
    if(l==r){
        t[o]=1e9;
        nex[o]=l;
        return ;
    }
    build(ls,l,mid);
    build(rs,mid+1,r);
    t[o]=min(t[ls],t[rs]);
    nex[o]=nex[ls];
}
int pos[N];
void up(int o,int l,int r,int pos,int d){
    if(l==r){
        t[o]=d;
        nex[o]=l;
        return ;
    }
    if(pos<=mid)up(ls,l,mid,pos,d);
    else up(rs,mid+1,r,pos,d);
    nex[o]=(t[ls]<t[rs]?nex[ls]:nex[rs]);
    t[o]=min(t[ls],t[rs]);
}
pii get(int o,int l,int r,int x,int y){
    if(x<=l&&r<=y){return {t[o],nex[o]};}
    pii Q={1e9,0};
    if(y>mid){
        pii X= get(rs,mid+1,r,x,y);
        Q=X;
    }
    if(x<=mid){
        pii X=get(ls,l,mid,x,y);
        if(X.fi<Q.fi)Q=X;
    }
    return Q;
}
int ans[N],G[N];
int main() {
	ios::sync_with_stdio(false);
    cin>>n;
    G[0]=1e9;
    build(1,1,n);
    for(int i=1;i<=n;i++)cin>>a[i],G[i]=1e9;
    cin>>m;
    for(int i=1;i<=m;i++)cin>>p[i].l>>p[i].r,p[i].i=i;
    sort(p+1,p+1+m);
    int l=1;
    for(int i=1;i<=m;i++){
        while(l<=p[i].r){
           if(pos[a[l]]){
               up(1,1,n,pos[a[l]],l);
           }
           up(1,1,n,l,pos[a[l]]);
           pos[a[l]]=l;
           l++;
        }
        pii res=get(1,1,n,p[i].l,p[i].r);
        if(res.fi>=p[i].l)ans[p[i].i]=0;
        else ans[p[i].i]=a[res.se];
    }
    for(int i=1;i<=m;i++)cout<<ans[i]<<'\n';
	return 0;
}