Дистанционная подготовка: RMQ за быстро
RMQ за быстро
от Алексей Золотов - Четверг 4 Декабрь 2008, 11:21
 

Можно ли сделать этот код чуть чуть быстрее. В задачена RMQ он почему-то не работает

#include <iostream>
using namespace std;
const int N=1000000;
int rmq[N],a[N];

int zapr(int l,int r,int v,int x,int y) {
    if (r<x || y<l) return 0;
    if (x<=l && r<=y) return rmq[v];
    int ll=zapr(l,(l+r)/2,v*2,x,y),rr=zapr((l+r)/2+1,r,v*2+1,x,y);
    if (a[ll]>a[rr]) return ll; else return rr;
}

void reload(int l,int r,int v) {
    if (l==r) {rmq[v]=l;return;}
    reload(l,(l+r)/2,v*2);reload((l+r)/2+1,r,v*2+1);
    if (a[rmq[v*2]]>a[rmq[v*2+1]]) rmq[v]=rmq[v*2]; else rmq[v]=rmq[v*2+1];
}

int n,k;
   
int main () {
    cin >> n;
    a[0]=-2000000000;
    for (int i=1;i<=n;i++) {
        cin >> a[i];
    }
    reload(0,n,1);
    cin >> k;
    for (int i=0;i<k;i++) {
        int l,r;
        cin >> l >> r;
        int ans=zapr(0,n,1,l,r);
        cout << a[ans] << ' ' << ans << endl;
    }
}
 

Хотя уже понятно - долго работает ввод/вывод