Multiples of 3

                                                  http://www.spoj.com/problems/MULTQ3/

                                         

MULTQ3 - Multiples of 3

#include<bits/stdc++.h>

using namespace std;

struct node
{
    int zer;
    int one;
    int two;
};

typedef struct node grp;
/*
 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;
}
*/
grp tre[10000000];
int a[1000000];
int lazy[1000000];


void built(int node,int st ,int en)
{
    if(st>en)
        return ;


   if(st==en)
   {
     tre[node].zer=1;
     tre[node].one=a[st];
     tre[node].two=a[st];
     return ;
   }

     built(2*node,st,(st+en)/2);
     built(2*node+1,1+(st+en)/2,en);
     tre[node].zer=tre[2*node].zer+tre[2*node+1].zer;
     tre[node].one=tre[2*node].one+tre[2*node+1].one;
     tre[node].two=tre[2*node].two+tre[2*node+1].two;
}





void update(int node,int st,int en,int fs,int fe)
{
   if(lazy[node]==1)    /// in this question lazy is just used as flag
   {
     int tmpzer=tre[node].zer;
     int tmpone=tre[node].one;
     int tmptwo=tre[node].two;

     tre[node].zer=tmptwo;
     tre[node].one=tmpzer;
     tre[node].two=tmpone;

     if(st!=en)
     {
       lazy[2*node]+= lazy[node];
       lazy[2*node]=lazy[2*node]%3;
       lazy[2*node+1]+=lazy[node];
       lazy[2*node+1]=lazy[2*node+1]%3;
     }
     lazy[node]=0;
   }
   else if(lazy[node]==2)
   {
     int tmpzer=tre[node].zer;
     int tmpone=tre[node].one;
     int tmptwo=tre[node].two;

     tre[node].zer=tmpone;
     tre[node].one=tmptwo;
     tre[node].two=tmpzer;

     if(st!=en)
     {
       lazy[2*node]+= lazy[node];
       lazy[2*node]=lazy[2*node]%3;
       lazy[2*node+1]+=lazy[node];
       lazy[2*node+1]=lazy[2*node+1]%3;
     }
     lazy[node]=0;
   }

   if(en<fs || st>fe || st>en)
     return;

   if(st>=fs && en<=fe)
   {
     int tmpzer=tre[node].zer;
     int tmpone=tre[node].one;
     int tmptwo=tre[node].two;

     tre[node].zer=tmptwo;
     tre[node].one=tmpzer;
     tre[node].two=tmpone;

       if(st!=en)
        {
         lazy[2*node]+= 1;
         lazy[2*node]=lazy[2*node]%3;
         lazy[2*node+1]+= 1;
         lazy[2*node+1]=lazy[2*node+1]%3;
        }
   }
   else
   {
    update(2*node,st,(st+en)/2,fs,fe);
    update(2*node+1,1+(st+en)/2,en,fs,fe);
     tre[node].zer=tre[2*node].zer+tre[2*node+1].zer;
     tre[node].one=tre[2*node].one+tre[2*node+1].one;
     tre[node].two=tre[2*node].two+tre[2*node+1].two;
   }
}








int  query(int node,int st,int en,int fs,int fe)
{
   if(lazy[node]==1)    /// in this question lazy is just used as flag
   {
     int tmpzer=tre[node].zer;
     int tmpone=tre[node].one;
     int tmptwo=tre[node].two;

     tre[node].zer=tmptwo;
     tre[node].one=tmpzer;
     tre[node].two=tmpone;

     if(st!=en)
     {
       lazy[2*node]+=lazy[node];
       lazy[2*node]=lazy[2*node]%3;
       lazy[2*node+1]+= lazy[node];
       lazy[2*node+1]=lazy[2*node+1]%3;
     }
     lazy[node]=0;
   }
   else if(lazy[node]==2)
   {
     int tmpzer=tre[node].zer;
     int tmpone=tre[node].one;
     int tmptwo=tre[node].two;

     tre[node].zer=tmpone;
     tre[node].one=tmptwo;
     tre[node].two=tmpzer;

     if(st!=en)
     {
       lazy[2*node]+= lazy[node];
       lazy[2*node]=lazy[2*node]%3;
       lazy[2*node+1]+= lazy[node];
       lazy[2*node+1]=lazy[2*node+1]%3;
     }
     lazy[node]=0;
   }

   if(en<fs || st>fe || st>en)
     return 0;

   if(st>=fs && en<=fe)
   {
     return tre[node].zer;
   }

     int f1=query(2*node,st,(st+en)/2,fs,fe);
     int f2=query(2*node+1,1+(st+en)/2,en,fs,fe);
      return f1+f2;
}



int main()
{
int n,q,i,j,k,l,ty,r;
scanf("%d%d",&n,&q);
//cin>>n>>q;
//n=read_int();
//q=read_int();

 for(i=0;i<n;i++)
  a[i]=0;

  built(1,0,n-1);

 for(i=0;i<q;i++)
 {
     scanf("%d%d%d",&ty,&l,&r);
   //cin>>ty>>l>>r;
  // ty=read_int();
  // l=read_int();
   //r=read_int();

   if(ty==0)
   {
    update(1,0,n-1,l,r);
   }
   else
   {
     int hh=query(1,0,n-1,l,r);
     printf("%d\n",hh);
   }
 }
return 0;
}