CF1000F One Occurrence题解

· · 个人记录

在线做法(O(mlog_25e5)巨慢无比
按照哈哈的项链，先处理出 pre 数组，pre[x] 表示 x 上一次出现的位置
那么问题就转化为求取 x∈[l,r] ，满足 x 是最靠右的且 pre[x]<l,此时，x必然是 [l,r] 中唯一的一个数
然后建树，考虑给右端点建树，把对应位置存入主席树里，维护 pre[x] 值，由于我们要求最靠右的，所以每次加新点把上一个位置清空就行
查询区间的时候把r的树取出来，把这里面 [l,r] 的子区间全部找出来，最多 2*log(5e5) 个，对其中每个子区间直接暴力求取合法的答案，若合法再求个答案，只有单个子区间是 log ，单次查询复杂度 log_2(5e5)
居然给我卡过去了。 

// Problem: CF1000F One Occurrence
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/CF1000F
// Memory Limit: 750 MB
// Time Limit: 3000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
using namespace std;

int read(){int x=0,f=1;char c=getchar();
    for(;c<'0'||c>'9';c=getchar()) if(c=='-') f=-1;
    for(;c>='0'&&c<='9';c=getchar()) x=(x<<3)+(x<<1)+(c^48);
    return x*f;
}
const int N = 5e5+10;
const int L = 20;
const int INF = 1e9+10;
const int qwq = 0;
const int qvq = 1;
const int MaxDat = 5e5;

int n,m,pre[N],dat[N];

int trcnt,T[N];
struct TREE{
    int ls,rs,val;
}t[N*L*2];
#define ls(x) t[x].ls
#define rs(x) t[x].rs
void Push_up(int x){t[x].val=min(t[ls(x)].val,t[rs(x)].val);}
int Mdfy(int pr,int x,int a,int b,int seat,int lim){
    if(!x) x=++trcnt,t[x].val=INF;
    if(!(a^b)) return t[x].val=lim,x;
    int mid=a+b>>1;
    if(seat<=mid) ls(x)=Mdfy(ls(pr),qwq,a,mid,seat,lim),rs(x)=rs(pr);
    else rs(x)=Mdfy(rs(pr),qwq,mid+1,b,seat,lim),ls(x)=ls(pr);
    Push_up(x);
    return x;
}
int RES(int x,int a,int b,int lim){
    if(!(a^b)) return t[x].val<lim?a:INF;int mid=a+b>>1;
    if(t[ls(x)].val<lim) return RES(ls(x),a,mid,lim);
    if(t[rs(x)].val<lim) return RES(rs(x),mid+1,b,lim);
    return INF;
}
int Qry(int x,int a,int b,int L,int R){
    if(L<=a&&b<=R) return RES(x,a,b,L);
    int mid=a+b>>1,res=INF;
    if(mid>=L) res=min(res,Qry(ls(x),a,mid,L,R)); 
    if(res!=INF) return res;//加速一下下下 
    if(mid+1<=R) res=min(res,Qry(rs(x),mid+1,b,L,R));
    return res;
}

signed main(){n=read();
    for(int i=1;i<=n;++i){dat[i]=read();int tmp;
        if(pre[dat[i]]) tmp=Mdfy(T[i-1],qwq,1,MaxDat,pre[dat[i]],INF);
        else tmp=T[i-1];
        T[i]=Mdfy(tmp,qwq,1,MaxDat,i,pre[dat[i]]);
        pre[dat[i]]=i;
    }
    m=read();
    for(int i=1;i<=m;++i){int l=read(),r=read();
        int k=Qry(T[r],1,MaxDat,l,r);
        printf("%d\n",dat[k==INF?0:k]);
    }
    return 0;
}

我真是个 zz ， 把位置和 lst 压一起就行了，不用多写一个函数 

// Problem: CF1000F One Occurrence
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/CF1000F
// Memory Limit: 750 MB
// Time Limit: 3000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
using namespace std;

int read(){int x=0,f=1;char c=getchar();
    for(;c<'0'||c>'9';c=getchar()) if(c=='-') f=-1;
    for(;c>='0'&&c<='9';c=getchar()) x=(x<<3)+(x<<1)+(c^48);
    return x*f;
}
const int N = 5e5+10;
const int L = 20;
const int INF = 1e9+10;
const int qwq = 0;
const int qvq = 1;
const int MaxDat = 5e5;

int n,m,pre[N],dat[N];

#define pii pair<int,int>
#define fi first
#define se second
int trcnt,T[N];
struct TREE{
    int ls,rs;
    pii val;
}t[N*L*2];
#define ls(x) t[x].ls
#define rs(x) t[x].rs
void Push_up(int x){t[x].val=min(t[ls(x)].val,t[rs(x)].val);}
int Mdfy(int pr,int x,int a,int b,int seat,int lim){
    if(!x) x=++trcnt,t[x].val.fi=INF;
    if(!(a^b)) return t[x].val.fi=lim,t[x].val.se=a,x;
    int mid=a+b>>1;
    if(seat<=mid) ls(x)=Mdfy(ls(pr),qwq,a,mid,seat,lim),rs(x)=rs(pr);
    else rs(x)=Mdfy(rs(pr),qwq,mid+1,b,seat,lim),ls(x)=ls(pr);
    Push_up(x);
    return x;
}
int Qry(int x,int a,int b,int L,int R){
    if(L<=a&&b<=R) return t[x].val.fi<L?t[x].val.se:INF;
    int mid=a+b>>1,res=INF;
    if(mid>=L) res=min(res,Qry(ls(x),a,mid,L,R)); 
    if(res!=INF) return res;//加速一下下下 
    if(mid+1<=R) res=min(res,Qry(rs(x),mid+1,b,L,R));
    return res;
}

signed main(){n=read();
    for(int i=1;i<=n;++i){dat[i]=read();int tmp;
        if(pre[dat[i]]) tmp=Mdfy(T[i-1],qwq,1,MaxDat,pre[dat[i]],INF);
        else tmp=T[i-1];
        T[i]=Mdfy(tmp,qwq,1,MaxDat,i,pre[dat[i]]);
        pre[dat[i]]=i;
    }
    m=read();
    for(int i=1;i<=m;++i){int l=read(),r=read();
        int k=Qry(T[r],1,MaxDat,l,r);
        printf("%d\n",dat[k==INF?0:k]);
    }
    return 0;
}