HackerEarth Array revolve problem solution

In this HackerEarth Array revolve problem solution You are given an array A(1-based index) consisting of N integers. You have to process two types of queries on this array.

HackerEarth Array revolves problem solution.

#include <stdio.h>
#include <iostream>
#include <map>
#include <vector>
#include <time.h>
#include <utility>
#include <cmath>
#include <set>
#include <cstring>
#include <algorithm>
using namespace std;
 
typedef long long int ll;
typedef pair<ll, ll> ipair;
#define mod 1000000007
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define rep(i,n) for(i=0;i<n;i++)
#define fu(i,a,n) for(i=a;i<=n;i++)
#define fd(i,n,a) for(i=n;i>=a;i--)
#define gi(n) scanf("%d",&n)
#define gl(n) scanf("%lld",&n)
#define pl(n) printf("%lld",n)
#define pi(n) printf("%d",n)
#define pp printf(" ")
#define pn printf("\n")
#define MAX 100005
#define LN 18

ll arr[MAX];
ll tree[4 * MAX];
ll lazy1[4 * MAX];
ll lazy2[4 * MAX];
ll inv;

ll calcNth(ll a, ll d, ll r) {
    ll val = (a + (r - 1) * d)%mod;
    return val;
}

ll calcSum(ll a, ll d, ll r) {
    ll sum = (2 * a + (r - 1) * d)%mod;
    sum = (sum * r)%mod;
    sum = (sum * inv)%mod;
    return sum;
}
void build(ll node, ll start, ll end) {
    if(start == end) {
        tree[node] = arr[start];
        return;
    }
    ll mid, p, q;
    mid = (start + end) >> 1;
    p = node << 1;
    q = p|1;
    build(p, start, mid);
    build(q, mid + 1, end);
    tree[node] = (tree[p] + tree[q])%mod;
}
void relax(ll node, ll start, ll end) {
    ll a = lazy1[node];
    ll d = lazy2[node];
    if(a || d) {
        ll sum = calcSum(a, d, end + 1 - start);
        tree[node] = (tree[node] + sum)%mod;
        if(start^end) {
            ll p = node << 1;
            ll q = p|1;
            ll mid = (start + end) >> 1;
            ll nth = calcNth(a, d, mid + 2 - start);
            lazy1[p] = (lazy1[p] + lazy1[node])%mod;
            lazy2[p] = (lazy2[p] + lazy2[node])%mod;
            lazy1[q] = (lazy1[q] + nth)%mod;
            lazy2[q] = (lazy2[q] + lazy2[node])%mod;
        }
        lazy1[node] = lazy2[node] = 0;
    }
}
void update(ll node, ll start, ll end, ll l, ll r, ll val, ll d) {
    relax(node, start, end);
    if(start > r || end < l) {
        return;
    }
    ll mid, p, q;
    mid = (start + end) >> 1;
    p = node << 1;
    q = p|1;
    if(start >= l && end <= r) {
        ll nval = calcNth(val, d, start + 1 - l);
        ll sum = calcSum(nval, d, end + 1 - start);
        tree[node] = (tree[node] + sum)%mod;
        if(start^end) {
            ll nth = calcNth(val, d, mid + 2 - l);
            lazy1[p] = (lazy1[p] + nval)%mod;
            lazy2[p] = (lazy2[p] + d)%mod;
            lazy1[q] = (lazy1[q] + nth)%mod;
            lazy2[q] = (lazy2[q] + d)%mod;
        }
        return;
    }
    update(p, start, mid, l, r, val, d);
    update(q, mid + 1, end, l, r, val, d);
    tree[node] = (tree[p] + tree[q])%mod;
}
ll query(ll node, ll start, ll end, ll l, ll r) {
    if(start > r || end < l) {
        return 0;
    }
    relax(node, start, end);
    if(start >= l && end <= r) {
        return tree[node];
    }
    ll mid, p, q;
    mid = (start + end) >> 1;
    p = node << 1;
    q = p|1;
    ll left = query(p, start, mid, l, r);
    ll right = query(q, mid + 1, end, l, r);
    return (left + right)%mod;
}
int main() {
    inv = 500000004;
    ll n, q;
    gl(n);
    gl(q);
    ll i;
    fu(i, 1, n) {
        gl(arr[i]);
    }
    build(1, 1, n);
    while(q--) {
        int ch;
        gi(ch);
        if(ch == 1) {
            ll id, val;
            gl(id);
            gl(val);
            ll num = n + 1 - id;
            if(val <= num) {
                update(1, 1, n, id, id + val - 1, val, mod - 1);
            }
            else {
                update(1, 1, n, id, n, val, mod - 1);
                val = val - num;
                ll k = val/n;
                ll st = calcSum(val, mod - n, k);
                update(1, 1, n, 1, n, st, mod - k);
                val = val%n;
                if(val) {
                    update(1, 1, n, 1, val, val, mod - 1);
                }
            }
        }
        else {
            ll l, r;
            gl(l);
            gl(r);
            if(l <= r) {
                ll ans = query(1, 1, n, l, r);
                pl(ans);
                pn;
            }
            else {
                ll ans = (query(1, 1, n, l, n) + query(1, 1, n, 1, r))%mod;
                pl(ans);
                pn;
            }
        }
    }
    return 0;
}

Second solution

#include <bits/stdc++.h>
using namespace std;

#define ms(s, n) memset(s, n, sizeof(s))
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define FORd(i, a, b) for (int i = (a) - 1; i >= (b); --i)
#define FORall(it, a) for (__typeof((a).begin()) it = (a).begin(); it != (a).end(); it++)
#define sz(a) int((a).size())
#define present(t, x) (t.find(x) != t.end())
#define all(a) (a).begin(), (a).end()
#define uni(a) (a).erase(unique(all(a)), (a).end())
#define pb push_back
#define pf push_front
#define mp make_pair
#define fi first
#define se second
#define prec(n) fixed<<setprecision(n)
#define bit(n, i) (((n) >> (i)) & 1)
#define bitcount(n) __builtin_popcountll(n)
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> pi;
typedef vector<int> vi;
typedef vector<pi> vii;
const int MOD = (int) 1e9 + 7;
const int FFTMOD = 119 << 23 | 1;
const int INF = (int) 1e9 + 23111992;
const ll LINF = (ll) 1e18 + 23111992;
const ld PI = acos((ld) -1);
const ld EPS = 1e-9;
inline ll gcd(ll a, ll b) {ll r; while (b) {r = a % b; a = b; b = r;} return a;}
inline ll lcm(ll a, ll b) {return a / gcd(a, b) * b;}
inline ll fpow(ll n, ll k, int p = MOD) {ll r = 1; for (; k; k >>= 1) {if (k & 1) r = r * n % p; n = n * n % p;} return r;}
template<class T> inline int chkmin(T& a, const T& val) {return val < a ? a = val, 1 : 0;}
template<class T> inline int chkmax(T& a, const T& val) {return a < val ? a = val, 1 : 0;}
inline ull isqrt(ull k) {ull r = sqrt(k) + 1; while (r * r > k) r--; return r;}
inline ll icbrt(ll k) {ll r = cbrt(k) + 1; while (r * r * r > k) r--; return r;}
inline void addmod(int& a, int val, int p = MOD) {if ((a = (a + val)) >= p) a -= p;}
inline void submod(int& a, int val, int p = MOD) {if ((a = (a - val)) < 0) a += p;}
inline int mult(int a, int b, int p = MOD) {return (ll) a * b % p;}
inline int inv(int a, int p = MOD) {return fpow(a, p - 2, p);}
inline int sign(ld x) {return x < -EPS ? -1 : x > +EPS;}
inline int sign(ld x, ld y) {return sign(x - y);}
mt19937 mt(chrono::high_resolution_clock::now().time_since_epoch().count());
inline int myrand() {return abs((int) mt());}
#define db(x) cerr << #x << " = " << (x) << " ";
#define endln cerr << "\n";

const int maxn = 1e5 + 5;
int n, q;
int a[maxn];

int st[maxn << 2];
int lz[maxn << 2][2];
void push(int p, int L, int R) {
    if (lz[p][0]) {
        addmod(st[p], mult(R - L + 1, lz[p][0]));
        if (L < R) {
            FOR(i, 0, 2) {
                addmod(lz[p << 1 | i][0], lz[p][0]);
            }
        }
        lz[p][0] = 0;
    }
    if (lz[p][1]) {
        addmod(st[p], mult((long long) (L + R) * (R - L + 1) / 2 % MOD, lz[p][1]));
        if (L < R) {
            FOR(i, 0, 2) {
                addmod(lz[p << 1 | i][1], lz[p][1]);
            }
        }
        lz[p][1] = 0;
    }
}
void upd0(int p, int l, int r, int L, int R, int val) {
    push(p, L, R);
    if (R < l || r < L) return;
    if (l <= L && R <= r) {
        lz[p][0] = val;
        push(p, L, R);
        return;
    }
    upd0(p << 1, l, r, L, L + R >> 1, val);
    upd0(p << 1 | 1, l, r, (L + R >> 1) + 1, R, val);
    st[p] = (st[p << 1] + st[p << 1 | 1]) % MOD;
}
void upd1(int p, int l, int r, int L, int R, int val) {
    push(p, L, R);
    if (R < l || r < L) return;
    if (l <= L && R <= r) {
        lz[p][1] = val;
        push(p, L, R);
        return;
    }
    upd1(p << 1, l, r, L, L + R >> 1, val);
    upd1(p << 1 | 1, l, r, (L + R >> 1) + 1, R, val);
    st[p] = (st[p << 1] + st[p << 1 | 1]) % MOD;
}
int query(int p, int l, int r, int L, int R) {
    push(p, L, R);
    if (R < l || r < L) return 0;
    if (l <= L && R <= r) return st[p];
    return (query(p << 1, l, r, L, L + R >> 1) + query(p << 1 | 1, l, r, (L + R >> 1) + 1, R)) % MOD;
}

void upd(int u, int v) {
    if (!v) return;
    if (u) {
        int nu = min(n - 1, u + v - 1);
        if (u <= nu) {
            upd0(1, u, nu, 0, n - 1, (u + v) % MOD);
            upd1(1, u, nu, 0, n - 1, MOD - 1);
            if (v - (nu - u + 1) > 0) {
                upd(0, v - (nu - u + 1));
            }
        }
    }
    else {
        int d = v / n;
        int r = v % n;
        int inc = mult(d, v);
        submod(inc, (long long) d * (d - 1) / 2 % MOD * n % MOD);
        addmod(inc, mult(d, u));
        upd0(1, 0, n - 1, 0, n - 1, inc);
        upd1(1, 0, n - 1, 0, n - 1, (MOD - d) % MOD);
        if (r) {
            int nv = r;
            int nu = u + nv - 1;
            upd0(1, u, nu, 0, n - 1, (u + nv) % MOD);
            upd1(1, u, nu, 0, n - 1, MOD - 1);
        }
    }
}

int query(int u, int v) {
    if (u > v) {
        return (query(u, n - 1) + query(0, v)) % MOD;
    }
    return query(1, u, v, 0, n - 1);
}

void chemthan() {
    cin >> n >> q;
    assert(1 <= n && n <= 1e5);
    assert(1 <= q && q <= 1e5);
    FOR(i, 0, n) {
        cin >> a[i];
        assert(1 <= a[i] && a[i] <= 1e9);
        upd0(1, i, i, 0, n - 1, a[i] % MOD);
    }
    while (q--) {
        int op, u, v; cin >> op >> u >> v;
        assert(1 <= op && op <= 2);
        if (op == 1) {
            u--;
            assert(0 <= u && u < n);
            assert(1 <= v && v <= 1e9);
            upd(u, v);
        }
        else {
            u--, v--;
            assert(0 <= u && u < n);
            assert(0 <= v && v < n);
            cout << query(u, v) << "\n";
        }
    }
}

int main(int argc, char* argv[]) {
    ios_base::sync_with_stdio(0), cin.tie(0);
    if (argc > 1) {
        assert(freopen(argv[1], "r", stdin));
    }
    if (argc > 2) {
        assert(freopen(argv[2], "wb", stdout));
    }
    chemthan();
    cerr << "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << "ms\n";
    return 0;
}