**Ý 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).**
#∈clude<bitsstdc++.h>#def∈elllonglong#def∈efifirst#def∈esesecondusingnamespacestd;const∫max
nhanmuaairi
Created at
3 likes