昨天Div4的H题，本来AC的，FST过后发现第40个测试点居然TM超时了

问题出在solve()中第二行的位置，定义了一个unordered_map，用来存每个数字出现过的下标

比赛中是用C+ +20提交的，如果把这里换成map就能AC，或者把提交语言换成C++14也能AC，并且执行时间都很短（31ms）

真是奇了大怪，哪位大佬能解释下么QAQ

#include<bits/stdc++.h>
using namespace std;

int n,a[200010],T;

void solve() {
    cin>>n;
    unordered_map<int,vector<int>>loc;//这里
    for(int i=1;i<=n;i++) {
        cin>>a[i];
        loc[a[i]].push_back(i);
    }
    int resa=0,resl=0,resr=0,mx=0;
    for(auto &i:loc) {
        vector<int>v=i.second;
        int nn=v.size();
        vector<int>b(nn+3,0),pmin(nn+3,1e9+10),rmin(nn+3,0);
        for(int k=0;k<nn;k++) {
            b[k]=v[k]-2*k;
        }
        for(int k=nn-1;k>=0;k--) {
            if(b[k]<=pmin[k+1]) {
                pmin[k]=b[k];
                rmin[k]=k;
            }
            else {
                pmin[k]=pmin[k+1];
                rmin[k]=rmin[k+1];
            }
        }
        for(int k=0;k<nn;k++) {
            int tmp=b[k]-pmin[k]+1;
            if(tmp>mx) {
                mx=tmp;
                resa=i.first;
                resl=v[k];
                resr=v[rmin[k]];
            }
        }
    }
    cout<<resa<<" "<<resl<<" "<<resr<<'\n';
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>T;
    while(T--) solve();
    return 0;
}

提问于22天前

岚秋

8933