竞技编程: "Time exceeded error"

Question

问题描述:

Task A. Amount of subtractions

You have an array a length n. There are m queries (l_i,r_i), for each of which it is necessary to find the sum of numbers sub-array [l_i,r_i]

Input data format:

The first line contains two integers n and m (1 ⩽ n, m ⩽ 10⁵) - the number of numbers and queries. The second line contains n integers a₁, a₂,. . . , a_n (1 ⩽ a_i ⩽ 10⁹) - the numbers of the array. Each of the following m lines contains two integer numbers l_i and r_i (1 ⩽ l_i ⩽ r_i ⩽ n) - the query.

Output data format:

For each request, take a separate line to answer it.

我的解决方案:

#include <stdio.h>

int main(void) {
    long n = 0;
    long m = 0;

    long l = 0;
    long r = 0;

    register long t = 0; // temporary variable, that contains intermediate results

    scanf("%ld%ld", &n, &m);

    long  a[n];
    long  tr[m]; // array, that contains results

    for (register long i = 0; i < n; i++)
        scanf("%ld", &a[i]);

    for (register long i = 0; i < m; i++) {
        scanf("%ld%ld", &l, &r);

        l--;
        r--;

        t = 0;
        if (l != r) {
            for (register long j = l; j <= r; j++)
                t += *(a + j);
        } else t = *(a + l);

        tr[i] = t; 
    }
    for (register long i = 0; i < m; i++)
        printf("%ld\n", tr[i]);


    return 0;
}

我的解决方案仅通过了 11 项测试中的 6 项。其他 5 项始终返回

Time exceeded error

我对竞技性编程还很陌生。 我应该如何优化我的代码以使大O复杂度低于O(n²)？ 任何帮助将不胜感激。

Answer 1

计算数组的累加和，并将其存储到另一个数组中，也就是说， Accumulated[i] = 数组中直到第 i 个索引的数字之和。这可以在 O(n) 中计算。

对于查询，答案将为accumulated[r] -cumulated[l]。这是 O(1)