MULTQ3 - Multiples of 3

MULTQ3 - Multiples of 3

#tree

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 (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. Each of the next Q lines are either of the form "0 A B" or "1 A B" as mentioned above.

Output :
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

--------------------------------------------------------code----------------------------------------------------------------------------

#include<iostream>

#include<stdio.h>

#define inf 100000;

using namespace std;

int lazy[10000000];

int qe, qs, upl,upu;

 int read_int()

 {

char r;

bool start=false,neg=false;

 int ret=0;

while(true){

r=getchar();

if((r-'0'<0 || r-'0'>9) && r!='-' && !start){

continue;

}

if((r-'0'<0 || r-'0'>9) && r!='-' && start){

break;

}

if(start)ret*=10;

start=true;

if(r=='-')neg=true;

else ret+=r-'0';

}

if(!neg)

return ret;

else

return -ret;

}

struct segment

{

  int def0;

   int def1;

   int def2;

}tree[1000010];

int temp0;

int temp3;

void build(int node, int start, int end)

{

if(start>end)

return ;

else if(start==end)

{

        tree[node].def0=1;

tree[node].def1=0;

tree[node].def2=0;

   return ;

}

build(2*node,start, (start+end)/2);

build(2*node+1,(start+end)/2+1,end);

tree[node].def0=tree[2*node].def0+tree[2*node+1].def0;

tree[node].def1=tree[2*node].def1+tree[2*node+1].def1;

tree[node].def2=tree[2*node].def2+tree[2*node+1].def2;

}

void updatetree(int node, int a, int b)

{

// cout<<a<<" "<<b<<endl;

if(lazy[node]!=0)

{

int val=lazy[node]%3;

if(val==1)

{

       temp0=tree[node].def0;

tree[node].def0=tree[node].def1;

tree[node].def1=tree[node].def2;

tree[node].def2=temp0;

if(a!=b)

{

lazy[2*node]+=lazy[node];      // the left child carries the due value that is to be updated from the parent node

lazy[2*node+1]+=lazy[node];   //the right child carries the due value that is to be updated from the parent node

}

lazy[node]=0;

  }

  if(val==2)

  {

     temp0=tree[node].def0;

  tree[node].def0=tree[node].def2;

   tree[node].def2=tree[node].def1;

   tree[node].def1=temp0;

 // tree[node].def2=temp0;

if(a!=b)

{

lazy[2*node]+=lazy[node];      // the left child carries the due value that is to be updated from the parent node

lazy[2*node+1]+=lazy[node];   //the right child carries the due value that is to be updated from the parent node

}

    lazy[node]=0;

}

else

{

 if(a!=b)

{

lazy[2*node]+=lazy[node];      // the left child carries the due value that is to be updated from the parent node

lazy[2*node+1]+=lazy[node];   //the right child carries the due value that is to be updated from the parent node

}

    lazy[node]=0;

}

}

if(a>b || a>upu || b<upl)

return ;

if(a>=upl && b<=upu)

{

       temp0=tree[node].def0;

tree[node].def0=tree[node].def1;

tree[node].def1=tree[node].def2;

tree[node].def2=temp0;

if(a!=b)

{

lazy[2*node]++;;  //carrying the due value to the left and right child and retrun the value of the node fully in the range

lazy[2*node+1]++;

}

return  ;

}

updatetree(2*node,a,(a+b)/2);   //updating the left child

updatetree(2*node+1,(a+b)/2+1,b);   //updating the right child

tree[node].def0=tree[2*node].def0+tree[2*node+1].def0;

tree[node].def1=tree[2*node].def1+tree[2*node+1].def1;

tree[node].def2=tree[2*node].def2+tree[2*node+1].def2;

}

int query(int node, int a ,int b)

{

     if(a>b || a>qe || b<qs )

return 0;

if(lazy[node]!=0)

{

if(lazy[node]!=0)

  {

int val=lazy[node]%3;

if(val==1)

{

       temp0=tree[node].def0;

tree[node].def0=tree[node].def1;

tree[node].def1=tree[node].def2;

tree[node].def2=temp0;

if(a!=b)

{

lazy[2*node]+=lazy[node];      // the left child carries the due value that is to be updated from the parent node

lazy[2*node+1]+=lazy[node];   //the right child carries the due value that is to be updated from the parent node

}

lazy[node]=0;

  }

  if(val==2)

  {

     temp0=tree[node].def0;

  tree[node].def0=tree[node].def2;

   tree[node].def2=tree[node].def1;

   tree[node].def1=temp0;

//  tree[node].def2=temp1;

if(a!=b)

{

lazy[2*node]+=lazy[node];      // the left child carries the due value that is to be updated from the parent node

lazy[2*node+1]+=lazy[node];   //the right child carries the due value that is to be updated from the parent node

}

    lazy[node]=0;

}

else

{

 if(a!=b)

{

lazy[2*node]+=lazy[node];      // the left child carries the due value that is to be updated from the parent node

lazy[2*node+1]+=lazy[node];   //the right child carries the due value that is to be updated from the parent node

}

    lazy[node]=0;

}

}

}

if(a>=qs && b<=qe)

{

return tree[node].def0;

}

    int q1=query(2*node, a,(a+b)/2);

     int q2=query(2*node+1,(a+b)/2+1,b);

     int res=q1+q2;

    return res;

}

int main()

{

int n;

int t;

//cin>>n>>t;

n=read_int();

t=read_int();

build(1,0,n-1);

/* for(int i=1;i<=5;i++)

{

cout<<i<<" "<<tree[i].def0<<" "<<tree[i].def1<<" "<<tree[i].def2<<endl;

}*/

while(t--)

{

int a;

//cin>>a;

a=read_int();

if(a==0)

{

//cin>>upl;

//cin>>upu;

upl=read_int();

upu=read_int();

// cin>>value;

updatetree(1,0,n-1);

/* for(int i=1;i<=9;i++)

{

cout<<i<<" "<<lazy[i]<<endl;

}*/

}

if(a==1)

{

//cin>>qs;

//cin>>qe;

qs=read_int();

qe=read_int();

//cout<<query(1,0,n-1)<<endl;

int ans=query(1,0,n-1);

printf("%d \n",ans);

}

}

return 0;

}