**Ý tưởng bài này như sau:**
Với mỗi giá trị a[i] thì bạn phải tìm vị trí a[j] sao cho j<i và a[j]=a[i], thì ta lưu vào pre[].
Với pre[i]=j thì nếu trong 1 truy vấn là l->r thì a[i] và a[pre[a[i]]] không thể cùng tồn tại.
Đồng nghĩa là pre[i] sẽ phải <=l.
Nên bài này ta sẽ tìm min của mảng pre[] trong đoạn từ l đến r.
Vì thế nên ta sẽ duyệt qua mỗi giá trị của a[i] và sửa đổi giá trị của pre[i] khi tìm thấy a[i].
Nói 1 cách dễ hiểu hơn là khi duyệt đến i thì pre[pre[a[i]]]=inf để đánh dấu rằng trong đoạn l->r
đã có 1 giá trị a[i].
Ta có một vài trường hợp như sau:
- Nếu trong đoạn l->r, số lần xuất hiện giá trị a[i] là 1, thì khi này pre[i]<l nên khi ta
update pre[pre[i]] thì cũng chả ảnh hưởng.
- Nếu trong đoạn l->r, số lần xuất hiện giá trị a[i] là >1 thì khi này pre[i]>=l ta sẽ cập nhật
pre[pre[i]]=inf nên vị trí pre[i] sẽ không được chọn, và dĩ nhiên rằng vị trí i cũng như vậy do
pre[i] đã >=l.
Vậy đáp án sẽ là i nếu pre[i] nhỏ nhất và pre[i]<l.
**Các bước thực hiện:**
- Tìm pre[i] với từng giá trị của i;
- Sort các truy vấn tăng dần theo r;
- Thực hiện quét qua các truy vấn và a[i]
**Độ phức tạp O(nlogn).**
```
#include<bits/stdc++.h>
#define ll long long
#define fi first
#define se second
using namespace std;
const int maxn=2e5;
struct name{
int l,r,id,ans;
};
name qe[maxn+5];
pair<int,int>t[maxn<<2],b[maxn+5];
int n,q,a[maxn+5],id=0,pre[maxn+5];
inline pair<int,int>push(const pair<int,int>&a,const pair<int,int>&b){
if(a.se<b.se)return a;
return b;
}
void up(int id,int l,int r,int u,int v){
if(l==r){
t[id]={l,v};
return;
}
int mid=l+r>>1;
if(u<=mid)up(id<<1,l,mid,u,v); else up(id<<1|1,mid+1,r,u,v);
t[id]=push(t[id<<1],t[id<<1|1]);
}
pair<int,int> get(int id,int l,int r,int u,int v){
if(u<=l&&v>=r) return t[id];
if(u>r||v<l) return {0,maxn+5};
int mid=l+r>>1;
return push(get(id<<1,l,mid,u,v),get(id<<1|1,mid+1,r,u,v));
}
int main(){
cin.tie(0)->sync_with_stdio(0); cout.tie(0);
cin>>n>>q;
for(int i=1;i<=4*n;i++){
t[i]={0,0};
}
for(int i=1;i<=n;i++){
cin>>a[i];
b[i]={a[i],i};
}
sort(b+1,b+n+1,[](const pair<int,int>&a,const pair<int,int>&b){
if(a.fi==b.fi)return a.se<b.se;
return a.fi<b.fi;
});
for(int i=2;i<=n;i++){
if(b[i].fi==b[i-1].fi) pre[b[i].se]=b[i-1].se;
}
for(int i=1;i<=q;i++){
cin>>qe[i].l>>qe[i].r;
qe[i].id=i;
}
sort(qe+1,qe+q+1,[](const name&a,const name&b){
return a.r<b.r;
});
for(int i=1;i<=q;i++){
int l=qe[i].l,r=qe[i].r;
while(id<r){
id++;
up(1,1,n,id,pre[id]);
if(pre[id]>0){
pre[pre[id]]=id;
up(1,1,n,pre[id],id);
}
}
auto tmp=get(1,1,n,l,r);
if(tmp.se>=l)qe[i].ans=0; else qe[i].ans=a[tmp.fi];
}
sort(qe+1,qe+q+1,[](const name&a,const name&b){
return a.id<b.id;
});
for(int i=1;i<=q;i++){
if(qe[i].l==qe[i].r){
cout<<a[qe[i].l]<<'\n';
}else cout<<qe[i].ans<<'\n';
}
return 0;
}
```
nhanmuaairi
Created at
0 likes