Hello coders, today we are going to solve Multiples of 3 CodeChef Solution whose Problem Code is MULTQ3.
Task
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 3Sample 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);
vector<int> adj[N];
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
{
FastReader bu=new FastReader();
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);
}
static class FastReader
{
final private int BUFFER_SIZE=1<<16;
private DataInputStream dis;
private byte[] buffer;
private int bufferPointer,bytesRead;
public FastReader()
{
dis=new DataInputStream(System.in);
buffer=new byte[BUFFER_SIZE];
bufferPointer=bytesRead=0;
}
public int nextInt() throws IOException
{
int ret=0;
byte c=read();
while(c<=' ') c=read();
boolean neg=(c=='-');
if(neg) c=read();
do
{
ret=ret*10+c-'0';
}while((c=read())>='0' && c<='9');
if(neg) return -ret;
return ret;
}
private void fillBuffer()throws IOException
{
bytesRead=dis.read(buffer,bufferPointer=0,BUFFER_SIZE);
if(bytesRead==-1) buffer[0]=-1;
}
private byte read() throws IOException
{
if(bufferPointer==bytesRead) fillBuffer();
return buffer[bufferPointer++];
}
}
}
Disclaimer: The above Problem (Multiples of 3) is generated by CodeChef but the Solution is Provided by CodingBroz. This tutorial is only for Educational and Learning Purpose.