# Multiples of 3 | CodeChef Solution

Hello coders, today we are going to solve Multiples of 3 CodeChef Solution whose Problem Code is MULTQ3.

There are N numbers a[0],a[1]..a[N – 1]. Initally all are 0. You have to perform two types of operations :

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”.

## Input Format

The first line contains two integers, N and Q. Each of the next Q lines are either of the form “0 A B” or “1 A B” as mentioned above.

## Output Format

Output 1 line for each of the queries 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```

## Constraints

• 1 <= N <= 100000
• 1 <= Q <= 100000
• 0 <= A <= B <= N – 1

## Solution – Multiples of 3

### C++

```#include "bits/stdc++.h"
using namespace std;

#define endl "\n"
#define tab "\t"
#define int long long
#define fastio ios_base::sync_with_stdio(0), cin.tie(NULL), cout.tie(NULL)
#define F first
#define S second
#define pi pair<int, int>
#define maxpq priority_queue<int>
#define minpq priority_queue<int, vector<int>, greater<int>>
#define inf (int) (1e18)
#define vi vector<int>
#define vpi vector<pi>
#define sz(v) (int)v.size()
#define for0(i, n) for(int i = 0; i < n; i++)
#define pb emplace_back
#define prec(n) fixed<<setprecision(n)
#define debug(x) cout << #x << ": " << x << endl

const int mod = (int)(1e9 + 7);
const int MAXN =  (int)((1e5) + 100);
int max(int a, int b) { if(a > b) return a; else return b;}
int min(int a, int b) { if(a > b) return b; else return a;}
int gcd(int a, int b) { if(a == 0) return b; return gcd(b%a, a);}
const int dx[4] = { 0, -1, 0, 1};
const int dy[4] = { -1, 0, 1, 0};
const int N = (int)(4 * 1e5 + 10);

void constructor()
{
fastio;
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif

}

//-----------------------------------------------------------------------------------
struct box
{
int zero, one, two;
};

box tree[N];
int lazy[N];

void buildTree(int index, int start, int end)
{
if(start == end)
{
tree[index].zero = 1;
tree[index].one = 0;
tree[index].two = 0;
return;
}

int mid = start + ((end - start) >> 1);
buildTree(2 * index, start, mid);
buildTree(2 * index + 1, mid + 1, end);

tree[index].zero = tree[2 * index].zero + tree[2 * index + 1].zero;
tree[index].one = tree[2 * index].one + tree[2 * index + 1].one;
tree[index].two = tree[2 * index].two + tree[2 * index + 1].two;
}

void shift(int index)
{
int temp0 = tree[index].zero;
int temp1 = tree[index].one;
int temp2 = tree[index].two;

tree[index].zero = temp2;
tree[index].one = temp0;
tree[index].two = temp1;
}

void handleLazy(int index, int start, int end)
{
if(lazy[index] > 0)
{
int temp = lazy[index];
lazy[index] = 0;

if(start != end)
{
lazy[2 * index] += temp;
lazy[2 * index + 1] += temp;
}
temp %= 3;

for(int i = 0; i < temp; i++)
shift(index);
}
}

void update(int index, int start, int end, int L, int R)
{
handleLazy(index, start, end);

if(end < L || R < start)
return;
else if(L <= start && end <= R)
{
shift(index);

if(start != end)
{
lazy[2 * index]++;
lazy[2 * index + 1]++;
}
return;
}

int mid = start + ((end - start) >> 1);
update(2 * index, start, mid, L, R);
update(2 * index + 1, mid + 1, end, L, R);

tree[index].zero = tree[2 * index].zero + tree[2 * index + 1].zero;
tree[index].one = tree[2 * index].one + tree[2 * index + 1].one;
tree[index].two = tree[2 * index].two + tree[2 * index + 1].two;
}

int query(int index, int start, int end, int L, int R)
{
handleLazy(index, start, end);

if(end < L || R < start)
return 0;
else if(L <= start && end <= R)
return tree[index].zero;

int mid = start + ((end - start) >> 1);
int left = query(2 * index, start, mid, L, R);
int right = query(2 * index + 1, mid + 1, end, L, R);
return left + right;
}

void runtestcase()
{

int n, q, type, L, R;
cin >> n >> q;
buildTree(1, 0, n - 1);

while(q--)
{
cin >> type;
if(type == 0)
{
cin >> L >> R;
update(1, 0, n - 1, L, R);
}
else
{
cin >> L >> R;
cout << query(1, 0, n - 1, L, R) << endl;
}
}
}

signed main(){

constructor();
int tc=1;
//cin >> tc;
while(tc--)
runtestcase();
return 0;
}
```

### Java

```import java.io.*;

class Spoj
{
static int n,q;
static Node st[];    //segment tree

public static void main(String args[])throws Exception
{
BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));
StringBuilder sb=new StringBuilder();
n=bu.nextInt(); q=bu.nextInt();
st=new Node[n<<2];
build(1,0,n-1);

while(q-->0)
{
int op=bu.nextInt(),x=bu.nextInt(),y=bu.nextInt();
if(op==0) update(1,0,n-1,x,y);
else bw.write(query(1,0,n-1,x,y)+"\n");
}
bw.flush();
}

static class Node
{
int three,two,one,lazy;
Node()
{
three=two=one=lazy=0;
}
}

static void build(int i,int l,int r)
{
st[i]=new Node();
if(l==r) st[i].three=1;
else
{
int p=i<<1,mid=(l+r)>>1;
build(p,l,mid);
build(p+1,mid+1,r);
st[i].three=st[p].three+st[p+1].three;
}
}

static void propagate(int i,int l,int r)
{
if(l!=r)
{
int p=i<<1;
st[p].lazy+=st[i].lazy;
st[p+1].lazy+=st[i].lazy;
}
st[i].lazy%=3;

if(st[i].lazy==1)
{
int t=st[i].three;
st[i].three=st[i].one;
st[i].one=st[i].two;
st[i].two=t;
}
else if(st[i].lazy==2)
{
int t=st[i].three;
st[i].three=st[i].two;
st[i].two=st[i].one;
st[i].one=t;
}
st[i].lazy=0;
}

static void update(int i,int l,int r,int x,int y)
{
propagate(i,l,r);
if(l>=x && r<=y)
{
st[i].lazy++;
propagate(i,l,r);
return;
}
else if(l>y || r<x) return;
else
{
int p=i<<1, mid=(l+r)>>1;
update(p,l,mid,x,y);
update(p+1,mid+1,r,x,y);
st[i].three=st[p].three+st[p+1].three;
st[i].two=st[p].two+st[p+1].two;
st[i].one=st[p].one+st[p+1].one;
}
}

static int query(int i,int l, int r,int x,int y)
{
propagate(i,l,r);
if(l>y || r<x) return 0;
else if(l>=x && r<=y) return st[i].three;
int p=i<<1,mid=(l+r)>>1;
return query(p,l,mid,x,y)+query(p+1,mid+1,r,x,y);
}

{
final private int BUFFER_SIZE=1<<16;
private DataInputStream dis;
private byte[] buffer;

{
dis=new DataInputStream(System.in);
buffer=new byte[BUFFER_SIZE];
}

public int nextInt() throws IOException
{
int ret=0;
boolean neg=(c=='-');
do
{
ret=ret*10+c-'0';
if(neg) return -ret;
return ret;
}

private void fillBuffer()throws IOException
{