c++ - 如何减少这个问题的执行时间(即更快的代码)

Question

这个问题来自 Codechef.com [如果有人仍在解决这个问题，请在尝试之前不要进一步查看该帖子]，虽然它运行正确，但我需要使其更快。我是 c 初学者，c++。(我知道数组、字符串和指针，但不知道文件处理等)。那么有没有一种方法可以使这个程序运行得更快而不使其变得复杂(如果算法复杂也可以)。 如果你提到你遵循哪本书，我也会接受复杂的编码:)。 我目前正在关注罗伯特·拉福尔。 这是程序:-

有 N 个数字 a[0],a[1]..a[N - 1]。最初都是 0。您必须执行两种类型的操作:

1) 将索引 A 和 B 之间的数字加 1。这由命令“0 A B”表示

2) 回答索引 A 和 B 之间有多少个数可以被 3 整除。这用命令“1 A B”表示。

输入:

第一行包含两个整数，N 和 Q。接下来的 Q 行的每一行的形式都是“0 A B”或“1 A B”，如上所述。

输出:

为“1 A B”形式的每个查询输出 1 行，其中包含相应查询所需的答案。

示例输入:

4 7
1 0 3
0 1 2
0 1 3
1 0 0
0 0 3
1 3 3
1 0 3

示例输出:

4
1
0
2

约束:

1 <= N <= 100000
1 <= Q <= 100000
0 <= A <= B <= N - 1

这是我的解决方案:-

#include<stdio.h>

int main()
{
    unsigned int n; //amount of numbers taken
    scanf("%u",&n);

    unsigned int arr[n],q,a,b,count=0,j,i;
    short int c;
    scanf("%u",&q);//cases taken  
    for(i=0;i<n;++i)
    {
      arr[i]=0;
    }    


    for(i=0;i<q;++i)
    {
      scanf("%d%u%u",&c,&a,&b);//here a,b are A and B respectively and c is either 
                               //o or 1

      if(c==0)
      {
        for(j=a;j<=b;++j)
          arr[j]++;
      }


      if(c==1)
      {
        for(j=a;j<=b;++j)
        {
          if(arr[j]%3==0)
            count++;
        }
       printf("%u\n",count);
      }
      count=0;
    }  

}

Answer 1

1) Increase the numbers between indices A and B by 1. This is represented by the command "0 A B"

2) Answer how many numbers between indices A and B are divisible by 3. This is represented by the command "1 A B".

最初的数字是 0，因此可以被 3 整除。增加 1 使数字不可整除。下一个增量 - 数字仍然不可整除。第三次增量使数字再次整除。

可以尝试的第一个优化是不要让数字增长到 2 以上:如果在增量期间数字从 2 变为 3，请将其设置回零。现在搜索范围变成与 0 的简单比较。(这样数组将包含而不是其模 3 的数字。)

第二个优化是使用范围而不是普通数组，例如类似于RLE的东西:将具有相同整除性的所有相邻数字折叠成一个范围。该数组将包含如下结构，而不是数字:

struct extent {
   int start; /* 0 .. N-1; extent should have at least one number */
   int end;   /* 0 .. N   */
   int n;     /* 0, 1, 2; we are only interested in the result of % */
};

最初，该数组将包含覆盖所有数字的单个范围 {0, N, 0} 。在增量步骤期间，一个范围可能会被分割或与相邻的范围合并。这种表示会加快数字的计数，因为您不是逐一而是分块地遍历数组。 (如果所有范围仅包含一个元素，它仍然会降级为线性搜索。)

---

另一种方法可能是使用三个带有下标的集合来代替数组。集合#0将包含模3为0的所有数字的下标，集合#1 - 1，集合#2 - 2。因为在增量操作期间，我们需要进行搜索，而不是std::set。最好使用例如 std::bitset 每个位都标记属于该集合的数字的索引。

注意这样我们就根本不保留原始数字。我们隐式地只保留模 3 的结果。

在增量过程中，我们需要找到索引属于哪个集合，例如设置 #n，并将索引移动到下一个 (mod 3) 集合:将集合中的位设置为零 n ，将集合 n + 1 (mod 3) 中的位设置为 1 。现在，计算可被 3 整除的数字就像计算集合 #0 中的非零位一样简单。这可以通过创建一个临时 std::bitset 来完成。作为位范围为 [A,B] 的掩码设置为 1，使用临时集屏蔽 #0 并调用 std::bitset::count()在生成的位集上。