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 revolve problem solution


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;
}