7299. Multiples of 3

 

There are n numbers a0, a1, ..., an–1. Initially all are 0. You have to perform two types of operations:

1.      Increase the numbers between indices a and b (inclusive) by 1. This is represented by the command "0 a b"

2.      Answer how many numbers between indices a and b (inclusive) are divisible by 3. This is represented by the command "1 a b".

 

Input. The first line contains two integers n and q (1 ≤ n, q ≤ 100000). Each of the next q lines are either of the form "0 a b" or "1 a b" as mentioned above. It is known that 0 ≤ a ≤ b ≤ n – 1.

 

Output. Print one line for each query of the form "1 a b" containing the required answer for the corresponding query.

 

Sample input

4 7

1 0 3

0 1 2

0 1 3

1 0 0

0 0 3

1 3 3

1 0 3

 

Sample output

4

1

0

2

 

 

РЕШЕНИЕ

структуры данных – дерево отрезков

 

Анализ алгоритма

Реализуем дерево отрезков с групповой операцией увеличения на единицу на отрезке. Операцию увеличения будем проводить по модулю три. В каждой вершине будем хранить количество единиц и двоек на отрезке. Тогда число нулей на отрезке можно вычислить как количество всех чисел на отрезке минус количество нулей и единиц.

 

Реализация алгоритма

 

#include <cstdio>

#include <vector>

#include <cstring>

#include <algorithm>

#define MAX 100010

using namespace std;

 

struct node

{

  int ones, twos, add;

} st[4*MAX];

 

void Push(int v, int LeftPos, int Middle, int RightPos)

{

  if (st[v].add == 1)

  {

    st[2*v].add = (st[2*v].add + 1) % 3;

    int _Ones = st[2*v].ones;

    st[2*v].ones = (Middle - LeftPos + 1) - st[2*v].ones - st[2*v].twos;

    st[2*v].twos = _Ones;

 

    st[2*v+1].add = (st[2*v+1].add + 1) % 3;

    _Ones = st[2*v+1].ones;

    st[2*v+1].ones = (RightPos - Middle) - st[2*v+1].ones - st[2*v+1].twos;

    st[2*v+1].twos = _Ones;

  } else

  if (st[v].add == 2)

  {

    st[2*v].add = (st[2*v].add + 2) % 3;

    int _Twos = st[2*v].twos;

    st[2*v].twos = (Middle - LeftPos + 1) - st[2*v].ones - st[2*v].twos;

    st[2*v].ones = _Twos;

 

    st[2*v+1].add = (st[2*v+1].add + 2) % 3;

    _Twos = st[2*v+1].twos;

    st[2*v+1].twos = (RightPos - Middle) - st[2*v+1].ones - st[2*v+1].twos;

    st[2*v+1].ones = _Twos;

  }

  st[v].add = 0;

}

 

void IncValue(int v, int LeftPos, int RightPos, int Left, int Right)

{

  if (Left > Right) return;

 

  if ((LeftPos == Left) && (RightPos == Right))

  {

    st[v].add = (st[v].add + 1) % 3;

    int _Ones = st[v].ones;

    st[v].ones = (Right - Left + 1) - st[v].ones -  st[v].twos;

    st[v].twos = _Ones;

    return;

  }

 

  int Middle = (LeftPos + RightPos) / 2;

  Push(v,LeftPos,Middle,RightPos);

 

  IncValue(2*v, LeftPos, Middle, Left, min(Middle,Right));

  IncValue(2*v+1, Middle+1, RightPos, max(Left,Middle+1), Right);

 

  st[v].ones = st[2*v].ones + st[2*v+1].ones;

  st[v].twos = st[2*v].twos + st[2*v+1].twos;

}

 

int Query(int v, int LeftPos, int RightPos, int Left, int Right)

{

  if (Left > Right) return 0;

 

  if ((LeftPos == Left) && (RightPos == Right))

    return (RightPos - LeftPos + 1) - st[v].ones - st[v].twos;

 

  int Middle = (LeftPos + RightPos) / 2;

  Push(v,LeftPos,Middle,RightPos);

 

  return Query(2*v, LeftPos, Middle, Left, min(Middle,Right)) +

         Query(2*v+1, Middle+1, RightPos, max(Left,Middle+1), Right);

}

 

int i, L, R, type, pos, Value, n, m;

 

int main(void)

{

  memset(st,0,sizeof(st));

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

  for(i = 0; i < m; i++)

  {

    scanf("%d %d %d",&type,&L,&R);

    if (type)

      printf("%d\n",Query(1,0,n-1,L,R));

    else

      IncValue(1,0,n-1,L,R);

  }

  return 0;

}