Оптимизировать дерево сегментов для максимальных запросов диапазона?

Question

Так что мне нужна помощь снова. Недавно я начал делать проблемы среднего уровня на кодеке, и поэтому я получаю TLE довольно много.

В основном вопрос заключается в том, чтобы найти сумму из нескольких запросов максимального диапазона, заданных в вопросе. Начальный диапазон задан, а следующие значения вычисляются по формуле, заданной в задаче.

Я использовал деревья сегментов для решения проблемы, но я продолжаю получать TLE для некоторых подзадач. Пожалуйста, помогите мне оптимизировать этот код.

Проблема ссылка- https://www.codechef.com/problems/FRMQ

//solved using segment tree 
#include <stdio.h> 
#define gc getchar_unlocked 
inline int read_int() //fast input function 
{ 
    char c = gc(); 
    while(c<'0' || c>'9') 
     c = gc(); 
    int ret = 0; 
    while(c>='0' && c<='9') 
    { 
     ret = 10 * ret + c - '0'; 
     c = gc(); 
    } 
    return ret; 
} 
int min(int a,int b) 
{ 
    return (a<b?a:b); 
} 
int max(int a,int b) 
{ 
    return (a>b?a:b); 
} 
void construct(int a[],int tree[],int low,int high,int pos) //constructs 
{           //the segment tree by recursion 
    if(low==high) 
    { 
     tree[pos]=a[low]; 
     return; 
    } 
    int mid=(low+high)>>1; 
    construct(a,tree,low,mid,(pos<<1)+1); 
    construct(a,tree,mid+1,high,(pos<<1)+2); 
    tree[pos]=max(tree[(pos<<1)+1],tree[(pos<<1)+2]); 
} 
int query(int tree[],int qlow,int qhigh,int low,int high,int pos) 
{ //function finds the maximum value using the 3 cases 
    if(qlow<=low && qhigh>=high) 
     return tree[pos];   //total overlap 
    if(qlow>high || qhigh<low) 
     return -1;     //no overlap 
    int mid=(low+high)>>1;   //else partial overlap 
    return max(query(tree,qlow,qhigh,low,mid,(pos<<1)+1),query(tree,qlow,qhigh,mid+1,high,(pos<<1)+2)); 
} 
int main() 
{ 
    int n,m,i,temp,x,y,ql,qh; 
    long long int sum; 
    n=read_int(); 
    int a[n]; 
    for(i=0;i<n;i++) 
     a[i]=read_int(); 
    i=1; 
    while(temp<n)  //find size of tree 
    { 
     temp=1<<i; 
     i++; 
    } 
    int size=(temp<<1)-1; 
    int tree[size]; 
    construct(a,tree,0,n-1,0); 
    m=read_int(); 
    x=read_int(); 
    y=read_int(); 
    sum=0; 
    for(i=0;i<m;i++) 
    { 
     ql=min(x,y); 
     qh=max(x,y); 
     sum+=query(tree,ql,qh,0,n-1,0); 
     x=(x+7)%(n-1);  //formula to generate the range of query 
     y=(y+11)%n; 
    } 
    printf("%lld",sum); 
    return 0; 
} 

Answer 1

Несколько заметок:

1. Это здорово вы используете быстрые процедуры ввода-вывода.
2. Убедитесь, что вы НЕ используете модульную операцию, потому что она очень медленная. Чтобы рассчитать остаток, просто вычтите N из числа, пока оно не станет меньше N. Это будет работать намного быстрее.
3. Ваш алгоритм работает в O ((M + N) * log N) времени, что не является оптимальным. Для статической задачи RMQ лучше и намного проще использовать sparse table. Для этого требуется O (N log N) и O (M + N log N).

Answer 2

Ну, я думаю, чтобы получить 100 баллов, вам нужно использовать разреженный стол.

Я пытался оптимизировать свой код https://www.codechef.com/viewsolution/7535957 (время выполнения снизился с 0,11 сек до 0,06 сек) , но все еще не достаточно, чтобы пройти подзадачу 3 ..