Операция с суммой массива

Question

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

Формулировка проблемы: -

Первоначально у вас есть перестановка идентичности N целых чисел в виде массива. Тождественная перестановка N целых чисел равна [1,2,3, ... N-1, N]. В этой задаче вы должны выполнить M операций над массивом и сообщить сумму элементов массива после каждой операции.

Операция i ^th состоит из целого числа op _i .

Если массив содержит op _i , поменяйте местами первый и последний элементы в массиве. В противном случае удалите последний элемент массива и pu sh op _i до конца массива. Формат ввода

Первая строка содержит два целых числа, разделенных пробелами: N и M . Затем следуют строки M , обозначающие операции op _i .

Ограничения:

2 <= N, M < = 10 ^ 5 </p>

1 <= op <= 5 * 10 ^ 5 </p>

Формат вывода

Выведите M строк, каждая из которых содержит одно целое число, обозначающее ответ на каждый из операции M.

Пример ввода 0

3 2
4
2

Пример вывода 0

7
7

Пояснение 0

Первоначально массив имеет вид [1, 2,3].

После 1-й операции массив становится [1,2,4] как op _i = 4, так как 4 отсутствует в текущем массиве, мы удаляем 3 и pu sh 4 до конца массива и, следовательно, sum = 7.

После 2-й операции массив становится [4,2,1] как op _i = 2 , поскольку в текущем массиве присутствует 2, мы меняем местами 1 и 4, и, следовательно, сумма = 7.

Вот мой код:

#include <bits/stdc++.h>

using namespace std;

 int main()

 {

    long int N,M,op,i,t=0;
    vector<long int > g1;
    cin>>N>>M;
    if(N>=2 && M>=2) {
    g1.reserve(N);
        for(i = 1;i<=N;i++) {
        g1.push_back(i);
    }
    while(M--) {

        cin>>op;
        auto it = find(g1.begin(), g1.end(), op);
            if(it != (g1.end())) {

                t = g1.front();
                g1.front() = g1.back();
                g1.back() = t;
                cout<<accumulate(g1.begin(), g1.end(), 0);
                cout<<endl;
            }
            else {

                g1.back() = op;
                cout<<accumulate(g1.begin(), g1.end(), 0);
                cout<<endl;
            }
            
        }
    }
    
    return 0;
}

Пожалуйста, предложите изменения.

Answer 1

моя догадка, давайте возьмем N = 3, op = [4, 2] N = [1,2,3] sum = ((N-2) * (N + 1)) / 2, он уйдет первым и последний элемент, укажите сумму чисел между ними.

нам нужно поиграть с первым и последним элементами. это большой o (n).

function performOperations(N, op) {
    let out = [];
    let first = 1, last = N;
    let sum = Math.ceil( ((N-2) * (N+1)) / 2);
    for(let i =0;i<op.length;i++){
        let not_between = !(op[i] >= 2 && op[i] <= N-1);
        if( first!= op[i] && last != op[i] && not_between) {
            last = op[i];
        }else {
            let t = first;
            first = last;
            last = t;
        }
        out.push(sum + first +last)
    }
    return out;
}

Answer 2

Внимательно присмотревшись к вопросу, вы обнаружите, что операции производятся только над первым и последним элементом. Таким образом, нет необходимости включать в него целый вектор, не говоря уже о вычислении суммы. мы можем вычислить всю сумму элементов, кроме первого и последнего, по (n + 1) (n-2) / 2, а затем мы можем манипулировать первым и последним элементами в вопросе. Мы также можем сократить поиск, используя (1