Как найти количество магазинов 3

Question

Это был конкурс Q:

Есть 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 строку для каждого из запросов формы "1 A B", содержащую требуемый ответ для соответствующего запроса.

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

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

Понятия не имею, как это решить. Вы можете помочь, пожалуйста?

Срок составляет 1 секунду. Я попробовал грубую силу, и я также попытался сохранить число делителей 3 перед i-м элементом для каждого i.

вот мой код C:

#include <stdio.h>


int nums[100*1000+20];
int d[100*1000+20];
int e[100*1000+20];
int dah[100*1000+20];

int main()
{
    int n,q;
    scanf("%d%d",&n,&q);
    int h;
    for(h=0;h<n;h++)
        {d[h/100]++; e[h/1000]++; dah[h/10]++;}
    int test;
    for(test=0;test<q;test++)
    {
        int op,start,end;
        scanf("%d%d%d",&op,&start,&end);
        if(0==op)
        {
            int x;
            for(x=start;x<=end;x++)
            {
                nums[x]++;
                nums[x]%=3;
                if(nums[x]==0)
                {
                    d[x/100]++;
                    e[x/1000]++;
                    dah[x/10]++;
                }
                else if(nums[x]==1)
                {
                    d[x/100]--;
                    e[x/1000]--;
                    dah[x/10]--;
                }
            }
        }
        else if(1==op)
        {
            int f;
            int ans=0;
            for(f=start;f<=end;)
            {
                if(f%1000==0&&f+1000<end)
                {
                    ans+=e[f/1000];
                    f+=1000;
                }
                else if(f%100==0&&f+100<end)
                {
                    ans+=d[f/100];
                    f+=100;
                }
                else if(f%10==0&&f+10<end)
                {
                    ans+=dah[f/10];
                    f+=10;
                }
                else
                {
                    ans+=(nums[f]==0);
                    f++;
                }
            }
            printf("%d\n",ans);
        }
    }
    return 0;
}

В этом подходе я сохраняю число, кратное 3, между k * 1000 и (k + 1) * 1000, а также то же самое для k * 100 и (k + 1) * 100, а также для 10. Это помогает мне запрос быстрее. но это все же дает мне превышение срока.

Answer 1

Подсказка № 1:

Подумайте, как вы можете использовать оператор MODULUS, чтобы помочь вам. Изначально у вас есть N чисел, скажем, N равно 5.

Таким образом, мы можем сохранить остатки для каждого номера (то есть сохранить 0 MOD 3, 1 MOD 3, 2 MOD 3 и т. Д.):

a[0] = 0
a[1] = 1
a[2] = 2
a[3] = 0
a[4] = 1
a[5] = 2

Каждый раз, когда вы увеличиваете диапазон чисел между A и B, вам действительно нужно хранить только 0, 1 или 2 в массиве. Например, если мы увеличиваем 2, то новым числом будет 3. Это теперь делится на 3, поэтому мы храним 0 в массиве. Таким образом, в случаях, когда у нас есть 0 и мы увеличиваем, мы храним 1, если у нас есть 1, мы храним 2, а если у нас 2, мы храним 0.

Эта оптимизация устраняет необходимость в любом делении, кроме начального шага. Деление - это очень дорогая операция, поэтому мы хотим устранить ее там, где можем.

Таким образом, после увеличения от 0 до 5 массив будет выглядеть так:

a[0] = 1
a[1] = 2
a[2] = 0
a[3] = 1
a[4] = 2
a[5] = 0

Количество чисел между A и B, которые делятся на 3, - это просто количество элементов, которые имеют 0 (в данном случае 2).

Теперь вам нужно подумать о том, как эффективно запросить диапазон от A до B, чтобы найти количество чисел, делимых на 3.

Подсказка № 2:

Чтобы выяснить, сколько чисел в интервале [A, B] делится на 3, можно использовать одну структуру алгоритма / данных - дерево сегментов. Читайте об этом здесь . Это выгодно для вас тем, что теперь вы можете очень быстро вычислить количество чисел, делимых на 3 для любого такого интервала [A, B], вместо того, чтобы перебирать массив и считать их.

Answer 2

Подсказка № 3:

Хорошее предложение от dcp.Хотя это не показывает, как решить проблему. Нет необходимости хранить все числа MOD 3 в массиве. Если числа обновляются каждый раз в массиве, сложность составляет O(Q * N), что явно слишком много для данных N, Q и1 сек.в худшем случае.Это точка Ali в комментарии к предложению dcp.

Число целых чисел с MOD%0, MOD%1, MOD%2 может храниться в каждом узле дерева сегментов.Следовательно, обновления могут быть сделаны в O(log N), что приводит к O(Q log N) только для обновлений.Для каждого запроса применяется одинаковая сложность O(log N).Поскольку вы знаете число целых чисел MOD% 3 для каждого остатка, нет необходимости переходить к всем листам ( каждый лист в дереве сегментов соответствует элементу массива ), чтобы определить, сколькочисла делятся на 3. Как только вы поймете, как работает дерево сегментов, должно быть понятно, почему необходимо хранить остатки в каждом узле дерева сегментов.Общая сложность алгоритма составляет O(Q log N), что хорошо вписывается в 1 sec. time limit.

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

Answer 3

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

Answer 4

какая верхняя граница для вашего массива? во-первых, понять это. Затем запланируйте чтение строк ввода в одной из этих двух форм. Строки в формате 0 A B просты в обращении, можете ли вы хотя бы так много кодировать? Если это так, опубликуйте его, а затем позаботьтесь о строках в формате 1 A B.