Codeforces Round #805 (Div. 3) C. Train and Queries

题意：给出一个长度为n的序列u，序列中的 ui 能到达其右侧的任意一个uj（i

分析：易知对于a若想到达b，那么a必须在b的左侧。在序列 u 中，ui可以出现若干次，故我们可以用map 储存 u 中 ui 出现的最大区间 ，然后根据该区间判断 a 是否能够到达 b。

#include

using namespace std;

const int N=2e5+10;

int a[N];

int main(){
    ios::sync_with_stdio(false);cin.tie(0);cin.tie(0);
    int t;
    cin >> t;
    while(t--){
    map> mp;
    int n,q;
    cin >> n >> q;
    for(int i=1;i<=n;i++){
        cin >> a[i];
        if(mp[a[i]].first==0)
            mp[a[i]].first=i;
        else
            mp[a[i]].first=min(i,mp[a[i]].first);// first 记录 a[i] 区间的左端点
        mp[a[i]].second=max(i,mp[a[i]].second); // second 记录 a[i] 区间的右端点
    }
    while(q--){
        int l,r;
        cin >> l >> r;
        if(mp[l].first==0 || mp[r].first==0){
            cout << "NO" << endl; // 若 l,r 的端点为0，说明l或r不在序列a中，故NO
            continue;
        }
        if(mp[l].first>mp[r].second) cout << "NO" << endl; // 若 l的左端点 大于 r的右端点 无法从l—>r 故NO
        else cout << "YES" << endl;
      }
   }
 return 0;
}