两个方法基本差不多，记住最近一次出现这个数的位置，就可以了。
RMQ ：
#include<iostream> #include<cstdio> #include<cstring> #include<string> #include<set> #include<map> #include<cmath> #include<algorithm> using namespace std; typedef long long ll; const int mx=5e5+10; int n,m,num[mx],kep[mx]; map <int,int> mp; int dp[mx][20]; void Rmq(){ for(int i=1;i<=n;i++) dp[i][0]=kep[i]; for(int j=1;(1<<j)<=n;j++){ for(int i=1;i+(1<<j)-1<=n;i++) dp[i][j]=max(dp[i][j-1],dp[i+(1<<(j-1))][j-1]); } } int query(int l,int r){ int len=r-l+1,k=log(len)/log(2.0); return max(dp[l][k],dp[r-(1<<k)+1][k]); } int main(){ while(cin>>n){ mp.clear(); for(int i=1;i<=n;i++){ scanf("%d",num+i); kep[i]=mp[num[i]]; mp[num[i]]=i; } Rmq(); scanf("%d",&m); int l,r; while(m--){ scanf("%d%d",&l,&r); int pos=query(l,r); if(pos<l) puts("OK"); else printf("%d\n",num[pos]); } puts(""); } return 0; }
线段树：
#include<iostream> #include<cstdio> #include<cstring> #include<string> #include<set> #include<map> #include<cmath> #include<algorithm> #define lson l,m,rt<<1 #define rson m+1,r,rt<<1|1 using namespace std; typedef long long ll; const int mx=5e5+10; int n,m,num[mx],kep[mx],sec[mx<<2]; map <int,int> mp; void push_up(int rt){ sec[rt]=max(sec[rt<<1],sec[rt<<1|1]); } void build(int l,int r,int rt){ if(l==r){ sec[rt]=kep[l]; return ; } int m=(l+r)>>1; build(lson); build(rson); push_up(rt); } int query(int l,int r,int rt,int L,int R){ if(L<=l&&R>=r) return sec[rt]; int m=(l+r)>>1,ans=0; if(m>=L) ans=max(ans,query(lson,L,R)); if(m<R) ans=max(ans,query(rson,L,R)); return ans; } int main(){ while(cin>>n){ mp.clear(); for(int i=1;i<=n;i++){ scanf("%d",num+i); kep[i]=mp[num[i]]; mp[num[i]]=i; } build(1,n,1); scanf("%d",&m); int l,r; while(m--){ scanf("%d%d",&l,&r); int pos=query(1,n,1,l,r); if(pos<l) puts("OK"); else printf("%d\n",num[pos]); } puts(""); } return 0; }
