CodeChef submission 558614 (C) plaintext list. Status: TLE, problem MULTQ3, contest . By shubh09 (shubh09), 2011-05-30 22:47:02.
//<O(log n),O(n)> (update time - O(log n), query time - O(n))
 
//working with r0,r1 - might cause a problem in this case, since we are trying to update in O(log n) time, which means that once we find a node of the segment tree which lies completely inside the range, we don't go and update its entire subtree...using r0,r1 like this - which might include deduction in values - will create complications as to how to imbibe those changes in its children and ancestors
 
//hence we are working with a single array instead, which takes into account the number added so far to the entire subtree
 
//not working for large inputs of N - not even 10000000...which was to be expected since an array of size of about n is being declared and using large arrays is not allowed...is there a workaround??
 
#include <stdio.h>
 
int min(int a,int b)
{
	if (a<b) return a;
	else return b;
}
 
int epow(int a, int b)
{
	if (b==0) return 1;
	if (b%2 == 0)
	{
		int temp = epow(a,b/2);
		return temp*temp;
	}
	return a*epow(a,b-1);
}
 
int logb2c(int n)		//calculates the ceiling of (log n (to the base 2))
{
	int i=1,j=0;
	while (i<n)
	{
		i*=2;
		j++;
	}
	return j;
}
 
void view(int node, int b, int e, int a[])
{
	printf("%d %d %d a-%d \n",node,b,e,a[node]);
	if (b!=e)
	{
		view((2*node),b,((b+e)/2),a);
		view((2*node)+1,((b+e)/2)+1,e,a);
	}
}
 
void initialize(int node, int b, int e,int a[])
{
	a[node]=0;
	if (b!=e)
	{
		initialize(2*node,b,(b+e)/2,a);
		initialize((2*node)+1,((b+e)/2)+1,e,a);
	}
}
 
void update1(int node, int b, int e, int r0[], int r1[])	//not used
{
	//base case - b=e
	int v = e-b+1;
/*	int r01 = min(v,r0[node]);
	int r12 = min(v,r1[node]);
	int r20 = min(v,v-r0[node]-r1[node]);
	int r0n = r0[node]-r01+r20;
*/
	int temp0,temp1;
	temp0=r0[node];
	temp1=r1[node];
	r0[node]=v-temp0-r1[node];
	r1[node]=temp0;
 
/*	int* change;
	*(change)=r0[node]-temp0;
	*(change+1)=r1[node]-temp1;
*/
	if (b!=e)
	{
		update1((2*node),b,(b+e)/2,r0,r1);
		update1((2*node)+1,((b+e)/2)+1,e,r0,r1);
	}
//	return change;
 
}
 
void backtrack(int node,int r0[], int r1[], int v0, int v1)	//not used
{
	r0[node]=r0[node]+v0;
	r1[node]=r1[node]+v1;
	if (node!=1) backtrack(node/2,r0,r1,v0,v1);
}
 
void update(int node, int b, int e, int i, int j, int a[])
{
	int change0,change1;
	if (j<b || i>e) {}
	else if (i<=b && j>=e)
	{
	//	int temp0 = r0[node],temp1=r1[node];
 
//		update1(node,b,e,r0,r1);
 
		a[node]++;
 
	//	change0=r0[node]-temp0;change1=r1[node]-temp1;
	//	if (node!=1) backtrack(node/2,r0,r1,change0,change1);
	}
	else// if (b!=e)
	{
		update((2*node),b,(b+e)/2,i,j,a);
		update((2*node)+1,((b+e)/2)+1,e,i,j,a);
	}
}
 
int query(int node, int b, int e, int i, int j, int a[], int num)
{
	int t = (num+(a[node]%3))%3;
	if (j<b || i>e) return 0;
	if (b==e) {if (t==0) return 1; else return 0;}
	else /*if (i<=b && j>=e)*/ return query((2*node),b,(b+e)/2,i,j,a,t) + query((2*node)+1,((b+e)/2)+1,e,i,j,a,t);
	//else return query((2*node),b,(b+e)/2,i,j,r0) + query((2*node)+1,((b+e)/2)+1,e,i,j,r0);
}
 
int main()
{	
	int n,q;
	scanf("%d %d", &n, &q);
	int height = logb2c(n)+1;
	int array_size=epow(2,height);
	int a1[array_size];		//numbering of nodes starts from 1
//	int rem0[array_size];
//	int rem1[array_size];
	initialize(1,0,n-1,a1);
	int i;
	int a,b,c;
	for (i=1;i<=q;i++)
	{
		scanf("%d %d %d", &a, &b, &c);
		if (a==0)	//update
		{
			update(1,0,n-1,b,c,a1);
		}
		else if (a==1)
		{
			printf ("%d\n",query(1,0,n-1,b,c,a1,0));
		}
		else if (a==2) view(1,0,n-1,a1);		//for checking purposes
	}
	return 0;
}