[ SPOJ ] MULTQ3 - Multiples of 3

Author            : Anwar Jahid Ruman Hossain 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : [ SPOJ ] MULTQ3 - Multiples of 3
Source            : Light OJ
Category          : Segment Tree
Algorithm         : Segment Tree
Verdict           : Time Limit Exceeded

1. #include<bits/stdc++.h>  
2. using namespace std;  
3. #define ll long long int  
4. #define mx 100005  
5. int tree[mx*3][3];  
6. int arr[mx];  
7. void build_segment(int node,int left,int right){  
8.     if(left==right){  
9.         tree[node][0] = 1;  //divisible by 3 means %3 = 0  
10.         tree[node][1] = 0;  // %3 = 1  
11.         tree[node][2] = 0;  // %3 = 2  
12.         return;  
13.     }  
14.     int mid=(left+right)/2;  
15.     build_segment(node*2, left, mid); //left subtree build  
16.     build_segment(node*2 + 1, mid+1, right); //right subtree build  
17.     tree[node][0] = tree[node*2][0] + tree[node*2+1][0];  
18.     tree[node][1] = tree[node*2][1] + tree[node*2+1][1];  
19.     tree[node][2] = tree[node*2][2] + tree[node*2+1][2];  
20. }  
21.   
22. int query_seqment(int node,int left,int right,int ia,int ib){  
23.     if(right < ia || left > ib)return 0;  
24.     if(ia <= left && right <= ib){  
25.         return tree[node][0];//the divisible count  
26.     }  
27.     int mid=(left+right)/2;  
28.     int cnt = 0;  
29.     cnt += query_seqment(node*2 + 1, mid+1, right, ia, ib); //right subtree query  
30.     cnt += query_seqment(node*2, left, mid, ia, ib); //left subtree query  
31.     return cnt;  
32. }  
33. void update_segment(int node,int left,int right, int ia,int ib){  
34.     if(ia>right || ib<left)  
35.         return;  
36.     if(left==right){  
37.         int tmp = tree[node][0];  
38.         tree[node][0] = tree[node][1];  
39.         tree[node][1] = tree[node][2];  
40.         tree[node][2] = tmp;  
41.         return;  
42.     }  
43.     int mid=(left+right)/2;  
44.     update_segment(node*2,left,mid,ia,ib);  
45.     update_segment(node*2+1,mid+1,right,ia,ib);  
46.     tree[node][0] = tree[node*2][0] + tree[node*2+1][0];  
47.     tree[node][1] = tree[node*2][1] + tree[node*2+1][1];  
48.     tree[node][2] = tree[node*2][2] + tree[node*2+1][2];  
49. }  
50. int main(){  
51.     ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);  
52.     //freopen("input.txt","r",stdin);  
53.     //freopen("output.txt","w",stdout);  
54.     int n,q;  
55.     while(scanf("%d%d",&n,&q)!=EOF){  
56.         build_segment(1,1,n);  
57.         int op,ia,ib;  
58.         for(int i=1;i<=q;i++){  
59.             scanf("%d%d%d",&op,&ia,&ib);  
60.             if(op==1)  
61.                 printf("%d\n",query_seqment(1,1,n,ia+1,ib+1));  
62.             else if(op==0){  
63.                 update_segment(1,1,n,ia+1,ib+1);  
64.             }  
65.         }  
66.     }  
67.     return 0;  
68. }