Оптимизация Стандартных итерационного алгоритма

Question

В связи с проблемной задачей здесь: Link

#include <iostream> 

using namespace std; 


int main() { 
    int T,*x,i,j,k,a,res,pres; 
    long Q,N,p,q; 
    cin>>T; 
    for(k=0;k<T;k++) 
    { 
     cin>>N>>Q; 
     x=new int[N]; 
     for(i=0;i<N;i++) 
     { 
      cin>>x[i]; 
     } 
     for(i=0;i<Q;i++) 
     { 
      pres=-999; 
      cin>>a>>p>>q; 
      for(j=p-1;j<q;j++) 
      { 
       res=a xor x[j]; 
       if(pres<res) 
       { 
        pres=res; 
       } 
      } 
      cout<<pres<<endl; 

     } 
     delete [] x; 
    } 
    return 0; 
} 

Я получаю Лимит времени превышено (подразумевая, что проблема может быть оптимизирована) на больших проблемах (N = 100000) (N , Q, T maxing out). Я полагаю, что мне нужно оптимизировать алгоритм, используя некоторую предварительную обработку. Мое решение - O (NQT) для всей проблемы. Проблема должна будет оценивать для всех возможных XOR для заданных лимитов в запросе. Итак, проблема должна будет идти (q-p) [Может быть в max N] раз для запроса. Я не могу понять, как избежать этого. Хит или направление было бы действительно оценено. Я думаю о реализации кучи как-то, так что он вычитает запрос a из кучи, и den делает максимальную кучу, чтобы увидеть максимальную разницу и den xors. Но это тоже будет принимать O (NQT)

Answer 1

Некоторые советы:

• Все звонки в cin сделать это невозможно измерить производительность этого кода. вы должны прочитать все данные заранее из файлов.
• Не выделяйте x каждый взгляд, выделите один раз malloc и позвоните realloc, чтобы сделать буфер более длинным, если необходимо. Распределение памяти может замедлить работу.

Внутренний цикл очень прост, поэтому компилятор может его векторизовать. Убедитесь, что это действительно происходит, глядя на разборку. Если нет, используйте встроенные функции SSE для работы по 4 или 8 8 элементам за раз.

Answer 2

Вот модифицированный код с предложениями, которые я сделал в комментариях.

Избегайте iostreams на C++ в коде, чувствительном к производительности. (FWIW, избегайте iostreams в целом) Избегайте распределения/освобождения как можно больше. В приведенном ниже коде vector::resize будет позаботиться о том, чтобы вектор всегда имел как минимум необходимое пространство. Непроизводительность, но удобство чтения: используйте пробелы оператора aronud. Объявить переменные закрыты , где они используются.

#include <cstdio> 
#include <vector> 
#include <algorithm> 

int main() { 
    int T; 
    std::vector<int> x; 

    std::scanf ("%d", &T); 
    for (int k = 0; k < T ; ++k) { 

     int N, Q; 
     std::scanf ("%d%d", &N, &Q); 
     x.resize (N); 

     for (int i = 0; i < N; ++i) 
      std::scanf ("%d", &x[i]); 

     for (int i = 0; i < Q; ++i) { 
      int a, p, q; 
      std::scanf ("%d%d%d", &a, &p, &q); 

      int pres = -999; 
      for(int j = p - 1; j < q; ++j) 
       pres = std::max (pres, a^x[j]); 

      std::printf ("%d\n", pres); 
     } 
    } 
    return 0; 
} 

Answer 3

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

С вопросом, я предполагаю, что они хотят что-то, что есть O (log N) для каждого запроса. Моя первоначальная мысль была segment tree, но я не мог найти способ использовать их для максимизации a^x[i].

Я считаю, что вы должны использовать тот факт, что все числа меньше 2^15. Другое дело, что вы хотите максимизировать операцию xor. Допустим, у вас есть (в двоичной системе)

a = b_1 b_2 ... b_n 

либо есть, что все x[j] с p <= j <= q имеют самый старший бит равен b_1, или есть некоторые x[j], для которых наиболее значащий бит является дополнением b_1. Это связано с тем, что b xor ~b = 1 для b in {0,1}. Вы выбираете только те j, для которых MSB является дополнением b_1, и продолжайте следующий бит (что соответствует b_2).

Проблема в том, что выполнение этой грубой силы хуже, чем то, что вы уже делаете, но это может помочь вам в более быстрой реализации.