[toph.co] Itachi's Challenge

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : Itachi's Challenge
Source            : toph.co
Category          : Data Structure
Algorithm         : Binary Indexed Tree, Range Update Range Query
Verdict           : Accepted

#include "bits/stdc++.h"
 
using namespace std;
 
#define ll       long long
 
static const int maxn = 1e5 + 5;
static const ll mod = 1e9 + 7;
 
ll bit1[maxn], bit2[maxn];
int telement, tquery;
int N;
 
inline void update(ll bit[], int pos, ll val)
{
      while (pos <= N)
      {
            bit[pos] = (bit[pos] + val);
            if (bit[pos] >= mod) bit[pos] -= mod;
            pos += (pos & -pos);
      }
}
 
inline ll query(ll bit[], int pos)
{
      ll sum = 0;
      while (pos > 0)
      {
            sum = (sum + bit[pos]);
            if (sum >= mod) sum -= mod;
            pos -= (pos & -pos);
      }
      return sum;
}
 
inline void rangeUpdate(int l, int r, ll val)
{
      ll rval = -val + mod;
      if (val >= mod) val -= mod;
      update(bit1, l, val); update(bit1, r+1, rval);
      update(bit2, l, (val * (l-1)) % mod); update(bit2, r+1, (rval*r) % mod);
}
 
inline ll rangeQuery(int l, int r)
{
      ll sumr = (query(bit1, r) * r - query(bit2, r) + mod) % mod;
      ll suml = (query(bit1, l-1) * (l-1) - query(bit2, l-1) + mod) % mod;
      return (sumr - suml + mod) % mod;
}
 
inline ll bigMod(ll a, ll p, ll m)
{
      if (p == 0) return 1;
      if (p == 1) return a;
      if (p & 1) return (a % m * bigMod(a, p - 1, m)) % m;
      ll ret = bigMod(a, p >> 1, m);
      return (ret % m * ret % m) % m;
}
 
inline ll modInv(ll a, ll m)
{
      return bigMod(a, m-2, m);
}
 
int main()
{
//      freopen("in.txt", "r", stdin);
 
      scanf("%d", &telement);
      N = telement;
      for (int i = 1; i <= telement; i++)
      {
            ll x;
            scanf("%lld", &x);
            rangeUpdate(i, i, x);
      }
      scanf("%d", &tquery);
      while (tquery--)
      {
            int l, r;
            ll k;
            scanf("%d %d %lld", &l, &r, &k);
            if (l > r) swap(l, r);
            ll sum = rangeQuery(l, r);
            ll mul = (bigMod(r-l+2, k, mod) - 1 + mod);
            if (mul >= mod) mul -= mod;
            mul = (mul * modInv(r-l+2-1, mod)) % mod;
            ll val = (sum * mul) % mod;
            rangeUpdate(l, r, val);
      }
      for (int i = 1; i <= telement; i++)
      {
            ll sum = rangeQuery(i, i);
            printf("%lld", sum);
            printf(i == telement ? "\n" : " ");
      }
}