题解 | #小苯的回文询问#

https://ac.nowcoder.com/acm/contest/78292/F

主要思路是在遍历输入数组 a 的过程中，维护一个辅助数组 L 和一个 map 来记录特定元素最后出现的位置。具体的过程如下：

1. 首先，声明一个哈希表 map<int, int> mp 用来记录每个元素最后出现的位置。

2. 开始遍历数组 a，对于每个元素 a[i]：

• 如果 mp 中已经存在元素 a[i]，则表示之前已经出现过该元素，此时如果上一个位置mp[a[i]]小于当前位置的前一个位置（即不相邻,<=i-2），则更新 L[i] 为 max(L[i], mp[a[i]])。
• 如果当前位置i>=3 并且 a[i] == a[i-2]，则也更新 L[i] 为 i-2。
• 更新 mp[a[i]] 为当前位置 i。

3. 在处理完整个数组后，得到了一个记录特定条件下位置的数组 L。

4. 接下来，对于每个查询区间 [l, r]：

• 如果查询的右边界 r 大于2 并且 L[r] 大于等于左边界 l，则输出 "YES"。否则，输出 "NO"。

**##### - 由此我们总结出每当出现扫描区间的判断时，要注意在r更新的同时，的区间内部的值是否会影响l的判断

******

#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
ll a[1000010];
ll L[1000010];
map<ll, ll> mp;

void solve(){
    ll n, q; cin>>n>>q;
    for(ll i=1; i<=n; i++){
        cin>>a[i]; L[i]=L[i-1];
        if(mp[a[i]]<i-1) L[i]=max(L[i], mp[a[i]]);  //更新左侧最右边满足条件的位置
        //a[i-1]==a[i]==a[i+1]需要特判，因为mp[a[i]]=i，所以不会进入上一行的if
        // 由此我们总结出每当出现扫描区间的判断时，要注意在r更新的同时，的区间内部的值是否会影响l的判断
        if(i>=3 && a[i]==a[i-2]) L[i]=i-2;
        mp[a[i]]=i;
    }
    while(q--){
        ll l, r; cin>>l>>r;
        if(L[r]>=l) cout<<"YES"<<endl;
        else cout<<"NO"<<endl;
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    ll T=1;
    while(T--){
        solve();
    }
    return 0;
}