SPOJ -> Multiples of 3

#include<bits/stdc++.h>
using namespace std;
int tree[400001][3];
int lazy[400001];
int query( int node , int  i , int  j , int s , int e )
{
           if(lazy[node] !=  0)
            {
               if( i!= j )
               {
                 lazy[2*node] = (lazy[node] + lazy[2*node])%3;
                 lazy[2*node+1] = ( lazy[node] + lazy[2*node+1])%3;
               }
               int a = tree[node][0];
               int b = tree[node][1];
               int c = tree[node][2];
               tree[node][1] = a;
               tree[node][2] = b;
               tree[node][0] = c;
               if(lazy[node] == 2)
               {
                   int a = tree[node][0];
                   int b = tree[node][1];
                   int c = tree[node][2];
                   tree[node][1] = a;
                   tree[node][2] = b;
                   tree[node][0] = c;
               }
               lazy[node] = 0;

            }

       if( i > j || s > j || e < i )
               return 0;

      if(s <= i && e >= j )
        return tree[node][0];

     return  query(2*node , i , (i+j)>>1 , s , e ) + query(2*node + 1 , ((i+j)>>1)+1 , j , s , e );

}
void update( int node , int  i , int  j , int s , int e )
{
            if(lazy[node] !=  0)
            {
               if( i!= j )
               {
                 lazy[2*node] = ( lazy[node] + lazy[2*node])%3;
                 lazy[2*node+1] = ( lazy[node] + lazy[2*node+1])%3;
               }
               int a = tree[node][0];
               int b = tree[node][1];
               int c = tree[node][2];
               tree[node][1] = a;
               tree[node][2] = b;
               tree[node][0] = c;
               if(lazy[node] == 2)
               {
                   int a = tree[node][0];
                   int b = tree[node][1];
                   int c = tree[node][2];
                   tree[node][1] = a;
                   tree[node][2] = b;
                   tree[node][0] = c;
               }
               lazy[node] = 0;

            }

       if( i > j || s > j || e < i )
               return;

      if(s <= i && e >= j )
      {
        int a = tree[node][0];
        int b = tree[node][1];
        int c = tree[node][2];
        tree[node][1] = a;
        tree[node][2] = b;
        tree[node][0] = c;
         if( i != j )
         {
           lazy[2*node] = ( 1 + lazy[2*node])%3;
           lazy[2*node+1] = ( 1 + lazy[2*node+1])%3;
         }
          return;
      }
       update(2*node , i , (i+j)>>1 , s , e );
       update(2*node + 1 , ((i+j)>>1)+1 , j , s , e );
       tree[node][0] = tree[2*node][0] + tree[2*node+1][0];
       tree[node][1] = tree[2*node][1] + tree[2*node+1][1];
       tree[node][2] = tree[2*node][2] + tree[2*node+1][2];



}
void build(int node , int i , int j )
{
      if( i > j )
       return;
     if(i == j)
      tree[node][0] = 1;
      else
      {
        build(2*node , i , (i+j) >> 1);
        build(2*node+1 , ((i+j) >> 1) + 1 , j);
        tree[node][0] = tree[2*node][0] + tree[2*node+1][0];
      }
}
int main(){


           int n , q;
           scanf("%d%d",&n,&q);

           build( 1 , 0 , n - 1);
        while( q-- )
        {
            int ch , l , r;
            scanf("%d%d%d",&ch,&l,&r);

            if(ch == 0)
            update( 1 , 0 , n - 1 ,  l , r );
            else
            printf("%d\n" , query( 1 , 0 , n - 1 , l , r ));


        }

        return 0;

}

SPOJ -> ARRAYSUB - subarrays

// sliding window algorithm
#include<bits/stdc++.h>
using namespace std;
int main(){


       int n , k , x ;
       cin >> n ;

       vector<int> vec;
       for(int i =  0 ; i < n ; ++i ){
          cin >> x;
          vec.push_back(x);
       }
       cin >> k;
        int mx = 0;
        vector<int> nval;
       for(int i =  0 ; i < n ; ++i ){

                  if(i%k == 0)
                   mx = vec[i];
                else
                mx = max( mx , vec[i] );
                nval.push_back(mx);
       }
       mx = 0;
       vector<int> val;
       for(int i = n-1 ; i >= 0 ; --i ){
             if(i%k == (k-1))
               mx = vec[i];
               else
               mx = max( mx , vec[i]);
               val.push_back(mx);

       }
       for(int i = 0 ; i < vec.size()-k+1  ; ++i )
             cout << max( nval[i+k-1] , val[val.size()-i-1]) <<" ";
             cout << endl;
             return 0;

}

SPOJ -> HORRIBLE - Horrible Queries

// using segmented tree with lazy update


#include<iostream>
#include<vector>
#include<algorithm>
#include<cmath>
#include<string>
#include<cstdio>
#include<cstring>
using namespace std;
long long  vec[400001];
long long lazy[400001];
long long retreive( long long  id ,  long long   i , long long  j , long long  s , long long e)
{
     if(i > j || s > j || e < i )
        return 0;
       if(s <= i && e >= j )
        return vec[id];
        else
            {
            long long mid = (i+j)/2;
      vec[2*id+1]+=(mid-i+1)*lazy[id];
      vec[2*id+2]+=(j-mid)*lazy[id];
      lazy[2*id+1]+=lazy[id];
      lazy[2*id+2]+=lazy[id];
      lazy[id]=0;

       return retreive(2*id+1,i,mid,s,e)+retreive(2*id+2,mid+1,j,s,e);
        }
}
void update( long long id , long long  i , long long j , long long s , long long e , long long val )
{
     if(i > j || e < i || s > j )
        return;
     if(s <= i && e >= j )
     {
         vec[id]+=(j-i+1)*val;
          lazy[id]+=val;
     }
     else {
            long long mid = (i+j)/2;
      vec[2*id+1]+=(mid-i+1)*lazy[id];
      vec[2*id+2]+=(j-mid)*lazy[id];
      lazy[2*id+1]+=lazy[id];
      lazy[2*id+2]+=lazy[id];
      lazy[id]=0;
     update(2*id+1,i,mid,s,e,val);
     update(2*id+2,mid+1,j,s,e,val);
     vec[id]=vec[2*id+1]+vec[2*id+2];
     }
}
int main()
{
     int t;
     scanf("%d",&t);
    while(t--){
    memset(lazy,0,sizeof lazy);
    memset(vec,0,sizeof vec);
             long long n , c;
              scanf("%lld%lld",&n,&c);
                        while(c--)
              {
                 long long  ch , p , q , v;
                 scanf("%lld%lld%lld",&ch,&p,&q);
                 if(ch==0)
                 {
                     scanf("%lld",&v);
                     update(0,0,n-1,p-1,q-1,v);
                 }
                 else {
                        long long ans = retreive( 0 , 0 , n-1, p-1, q-1);
                    printf("%lld\n",ans);

                 }
              }



    }
      return 0;
}

SPOJ -> HORRIBLE - Horrible Queries

// using sqrt decomposition

#include<bits/stdc++.h>
using namespace std;
int main(){
                       int t;
                       scanf("%d",&t);
                       while(t--){
    long long n , q , ch , l , r ,v,t1,t2 ,i ;
         scanf("%lld%lld",&n,&q);
           long long  arr[n+1];
      memset(arr,0,sizeof arr);
      //  for(int i  = 0 ; i < n ; ++i )
        //   scanf("%lld",&arr[i]);
        long long val = sqrt(n);
        long long sz = (n-1)/val;
        long long sq[sz+1][3];
        memset(sq,0,sizeof sq);
       // for( i = 0; i < n ; ++i )
         //   sq[i/val][1]=(sq[i/val][1]+arr[i])%mod;
               while(q--)
               {
                    scanf("%lld%lld%lld",&ch,&l,&r);
                   l--;
                    r--;
                      if(ch == 0)
                      {
                          scanf("%lld",&v );
                           t1 = l/val;
                           t2 = r/val;
                          for( i = l ; i/val==t1 && i <= r ; ++i )
                          {
                                arr[i] = (arr[i] + v);
                                sq[t1][1] = (sq[t1][1]+v);
                          }
                          for( i = t1+1 ; i < t2 ; ++i )
                              sq[i][2] = (sq[i][2] + v);
                              if(t1 != t2 )
                              for(int i = r ; i/val==t2 && i>=l; --i )
                              {
                                  arr[i] = (arr[i] + v);
                                  sq[t2][1] = (sq[t2][1]+v);
                              }
                                        }
                      else
                      {
                          long long ans = 0;
                           t1 = l/val;
                           t2 = r/val;
                          for( i = l ; i/val==t1 && i <= r ; ++i )
                              ans = (ans + (arr[i] + sq[t1][2]));
                          for( i = t1+1 ; i < t2 ; ++i )
                            ans = (ans + (sq[i][1]+(sq[i][2]*val)));
                               if(t1 != t2 )
                              for( i = r ; i/val==t2 && i>=l; --i )
                              ans = (ans + (arr[i] + sq[t2][2]));
                              printf("%lld\n",ans);
                      }

               }
                       }
           return 0;
}

SPOJ -> FIBOSUM - Fibonacci Sum

#include<bits/stdc++.h>
#define  ll  long long
#define mod 1000000007
using namespace std;
void mul( ll a[2][2] , ll b[2][2])
{
   ll c[2][2];
   for(int i =  0 ; i < 2 ; ++i ){
      for(int j =  0 ; j < 2 ; ++j ){

          c[i][j] = 0;
          for(int  k = 0 ; k < 2 ; ++k )
            c[i][j] = (c[i][j] + (a[i][k]*b[k][j])%mod)%mod;
      }


   }
    for(int i = 0 ; i < 2 ; ++i ){
      for(int j  = 0 ; j < 2;  ++j )
        a[i][j] = c[i][j];
      }

}
ll fib( ll n)
{
        if(n==0)
         return 0;
         if(n == 1)
         return 1;
         ll res[2][2]={{1,0},{0,1}} , mat[2][2] = {{1,1} ,{1,0}};
             while(n)
             {
               if(n%2!=0)
               mul(res,mat);
               n = n >> 1;
               mul(mat,mat);

             }

           return res[0][1];
}
int main()
{
               int t;
               cin >> t;
               while(t--)
               {
                     ll n ,  m;
                     cin >> n  >> m;

                     ll ans = fib(m+2) - 1;
                      ans = ans  - (fib(n+1)-1);
                      if(ans<0)
                      ans+=mod;
                      ans = ans%mod;
                      cout << ans << endl;


               }
     return 0;
}

SPOJ -> A_W_S_N - Happy Valentine Day (Valentine Maze Game)

#include<bits/stdc++.h>
using namespace std;
int ans;
void cst(int ar[12][12],int node , int dest , int size , int cost,int vis[12],int collect)
{
      if(cost > ans )
      return;
      if(node == dest)
      {
          if(collect == size)
          {
                ans = min(ans,cost);
                return;
          }

      }

     for(int i = 1 ; i <= size ; ++i )
     {
         if(vis[i] == 0 && i != node)
         {
             vis[i] = 1;
            cst(ar,i,dest,size,cost+ar[node][i],vis,collect+1);
            vis[i] = 0;
          }
     }

}
int main(){
          ios_base::sync_with_stdio(false);
            int t;
           cin >> t;
           while(t--){

              int n  , m;
              cin >> n >> m;

                string x[n+1];
                for(int i = 0 ; i < n ; ++i )
                    cin >> x[i];

                 vector<int> graph[10001];
                       int source;
                       int dest;
                       vector<int> choc;
                 for(int i = 0 ;  i < n ; ++i ){
                    for(int j = 0 ; j < m ; ++j )
                       {
                            if(x[i][j] != '#')
                            {
                       int node1 = i*m+(j+1);
                       if(x[i][j]=='C')
                         choc.push_back(node1);
                         else
                         if(x[i][j]=='T')
                          source = node1;
                          else
                          if(x[i][j] =='W')
                          dest = node1;
                                if(i+1 < n )
                                {
                                    int node2 = (i+1)*m+(j+1);
                                    graph[node1].push_back(node2);
                                    graph[node2].push_back(node1);
                                }
                                if(j+1<m)
                                {
                                 int node2 = i*m + (j+2);
                                    graph[node1].push_back(node2);
                                    graph[node2].push_back(node1);
                                }
                        }
                    }
                 }
                 int arr[12][12]={0};
                  int dist[10001];
                  int visit[10001];
                   for(int i = 0 ; i <= 10000 ; ++i ){
                      dist[i] = 1e9;
                      visit[i] = 0;
                   }
                     queue<int> q;
                     q.push(source);
                      dist[source] = 0 ;
                      while(!q.empty())
                      {
                          int u  = q.front();
                           q.pop();
                          if(visit[u] == 1)
                           continue;
                          for(int i = 0 ; i < graph[u].size() ; ++i )
                          {
                              int v = graph[u][i];
                              if(visit[v] == 0)
                              {
                                   if(dist[v] == 0)
                                  dist[v] = dist[u] + 1;
                                  else
                                  dist[v] = min(dist[v] , dist[u]+1);
                                   q.push(v);
                              }

                          }
                          visit[u] = 1;
                      }
                    for(int i = 0 ; i < choc.size() ; ++i )
                    {
                        arr[1][i+2] = dist[choc[i]];
                    }
                    arr[1][choc.size()+2] = dist[dest];
                    arr[choc.size()+2][1] = dist[dest];
                    for(int j = 0 ; j < choc.size() ; ++j )
                    {
                        for(int i = 0 ; i <= 10000 ; ++i )
                         {
                              dist[i] = 1e9;
                              visit[i] = 0;
                            }
                              q.push(choc[j]);
                      dist[choc[j]] = 0 ;
                      while(!q.empty())
                      {
                          int u  = q.front();
                           q.pop();
                          if(visit[u] == 1)
                           continue;
                          for(int i = 0 ; i < graph[u].size() ; ++i )
                          {
                              int v = graph[u][i];
                              if(visit[v] == 0)
                              {
                                  dist[v] = dist[u] + 1;
                                   q.push(v);
                              }

                          }
                          visit[u] = 1;
                      }
                      arr[j+2][1] = dist[source];
                      arr[j+2][choc.size()+2]= dist[dest];
                      arr[choc.size()+2][j+2]= dist[dest];
                     for(int i = 0 ; i < choc.size() ; ++i )
                         arr[j+2][i+2] = dist[choc[i]];
                      }
                      int size = choc.size()+2;
                      int flag = 0;
                      for(int i = 1 ; i <= size ; ++i )
                      {
                           for(int j = 1 ; j <= size ; ++j )
                               if(arr[i][j] == 1e9)
                                 flag = 1;
                      }
                          if(flag == 1)
                     cout <<"Mission Failed!"<<endl;
                     else{
                         ans = 1e9;
                         int vis[13]={0};
                           vis[1] = 1;
                        cst(arr,1,size,size ,0,vis,1);
                        cout << ans << endl;
                     }

           }
           return 0;
}

SPOJ -> ABCD - Colours A, B, C, D

#include<bits/stdc++.h>
using namespace std;
int main(){

       int  n;
       cin >> n;
       string x;

        cin >> x;
        string ans;

          for(int i = 0 ; i < 2*n ; i=i+2)
           {
                 int p1=-1;
                 int p2=-1;
                 int b[4]={1,1,1,1};
                 b[x[i]-'A']=0;
                 b[x[i+1]-'A']=0;
                 for(int j = 0 ; j < 4 ; ++j )
                 {
                     if(b[j]==1)
                     {
                         if(p1 == -1)
                         p1 = j;
                         else
                         p2 = j;
                     }


                 }
                  ans+=(p1+'A');
                  ans+=(p2+'A');
                  if(ans[i] == ans[i-1])
                   swap(ans[i],ans[i+1]);
           }
            cout << ans << endl;

    return 0;
          }

SPOJ -> POWERUP - Power the Power Up

#include<bits/stdc++.h>
#define MOD 1000000007
using namespace std;
long long fast(long long base , long long exp , long long mod)
{
   long long res = 1;
     while(exp){
       if(exp&1)
        res = (res%mod * base%mod) % mod;
        exp = exp >> 1;
        base = (base%mod * base%mod) % mod;
        }
        return res;

}
int main(){

                   while(true){

                       long long a , b , c;
                        cin >> a >> b >> c;
                        if(a == -1 &&  b == -1 && c == -1)
                             break;
                         if(c == 0)
                          cout << (a%MOD) <<endl;
                          else
                         if(b == 0)
                          cout <<"1" << endl;
                          else
                          if(a%MOD == 0)
                          cout <<"0"<<endl;
                          else {
                        long long result2 = fast( b , c , MOD-1);
                        long long result1 = fast(a , result2 , MOD);
                        cout << result1 << endl;
                      }
                   }
                   return 0;
}

SPOJ -> SUMPRO - SUM OF PRODUCT

#include<bits/stdc++.h>
#define  mod 1000000007
using namespace std;
int main(){

      int t;
      cin >> t;
      while(t--){

               long long  n , i ;
               cin >> n;
             long long ans = 0;
             long long last;
                 for( i = 1; i*i <= n ; ++i )
                       ans = (ans + (i * (n/i))%mod)%mod;
                     --i;
                     last = n/i;
                    for( i = 1; i < last ; ++i )
                    {
                        long long en = n/i;
                        long long st = n/(i+1);
                            long long diff = (en*(en+1)/2 )-  (st*(st+1)/2);
                              ans =  (ans + (i*diff)%mod)%mod;

                    }

                 cout << ans << endl;
      }

        return 0;

 }