Задача RMQ Fast

Question

Реализуйте структуру данных, которая на данном массиве из N целых чисел позволяет узнать максимальное значение на этом массиве и индекс элемента, на котором достигается это максимальное значение. Формат ввода В первой строке вводится натуральное число N ( 1 ≤ N ≤ 1 0 5 ) – количество элементов в массиве. В следующей строке содержатся N целых чисел, не превосходящих по модулю 10̂9 – элементы массива. Далее идет число K ( 0 ≤ K ≤ 1 0 5 ) – количество запросов к структуре данных. Каждая из следующих K строк содержит два целых числа l и r ( 1 ≤ l ≤ r ≤ N ) – левую и правую границы отрезка в массиве для данного запроса. Формат вывода Для каждого из запросов выведите два числа: наибольшее значение среди элементов массива на отрезке от l до r и индекс одного из элементов массива, принадлежащий отрезку от l до r , на котором достигается этот максимум.

Ограничение по времени 0.3 сек, по памяти 512мб Вот мой код: constexpr int kmax=17,nmax=100000; pii sparse[kmax][nmax];

pii get_max(int l,int r,vector<int>& deg){
    int k=deg[r-l+1];
    pii ans=mp(0,0);

ans.first=max(sparse[k][l].first,sparse[k][r-(1<<k)+1].first);
ans.second=(sparse[k][l].first>sparse[k][r-(1<<k)+1].first?sparse[k][l].second:sparse[k][r-(1<<k)+1].second);

return ans;
}

int main() {

int n,m,l,r;
cin>>n;

vector<int> a(n+1),deg(n+1);
for(int i=1;i<=n;++i)
    cin>>a[i];

cin>>m;

for(int i=1;i<=n;++i){
    sparse[0][i].first=a[i];
    sparse[0][i].second=i;

}

for(int k=0;k<kmax-1;++k)
for(int i=1;i<=n;++i){
    int j=min(i+(1<<k),n);
    sparse[k+1][i].first=max(sparse[k][i].first,sparse[k][j].first);
    sparse[k+1][i].second=(sparse[k+1][i].first==sparse[k][i].first?sparse[k][i].second:sparse[k][j].second);
}

deg[1]=0;
for(int a=2;a<=n;++a){
    deg[a]=deg[a-1];
    if(!(a&(a-1)))
        ++deg[a];
}

for(int i=0;i<m;++i){
    cin>>l>>r;
    pii tmp=get_max(l,r,deg);
    cout<<tmp.first<<' '<<tmp.second<<endl;
}

return 0;

}

Ловлю TL 348 ms. Как можно решить эту задачу? Я уже не знаю, как ускорить решение, разве есть что - то быстрее разреженной таблицы?

БЛОГ НА HUSL

Задача RMQ Fast

Ответы (0 шт):