In this HackerEarth Naruto - The New Hokage problem solution Naruto was declared as the 7th Hokage because of his great contribution in the 4th Shinobi World War. As soon as he acquires the office, he changes the process of ranking Shinobis. Instead of the Genin (Beginner), Chuunin (Intermediate), and Jounin (Expert), the new ranks are numbers ranging from 1 (lowest) to 10 (highest).
There are a total of N ninjas in the Leaf Village, ith of which has Ai amount of chakra (energy). A ninja with rank P would have the strength of AiP.
Naruto has Q pending tasks to perform which can be of one of the following types:-
1 i K: Update the result of the training of the ith ninja i.e. increase the amount of chakra of the ith ninja by K.
2 L R K: Update the result of the training of the ninjas ranging from L to R i.e. increase the amount of chakra of the ninjas ranging from L to R by K.
3 L R P: Calculate the total strength of the ninjas ranging from L to R provided that each of these ninjas has rank P for sending them to a mission assigned to the Leaf Village. As the value can be very large, calculate it modulo 10^9 + 7.
Naruto asked you to take care of these tasks.
HackerEarth Naruto - The New Hokage problem solution.
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <string.h>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <list>
#include <math.h>
#define ll long long int
#define maxN 1000000
#define maxVal 100000000
#define minVal -100000000
#define mod 1000000007LL
#define gcd(a,b) __gcd(a,b)
using namespace std;
ll n;
ll a[maxN+5];
ll tree[3*maxN+5][12];
ll lazy[3*maxN+5];
ll comb[12][12];
ll powmod(ll a,ll b)
{
ll x=1,y=a;
while(b>0)
{
if(b%2)
x=(x*y)%mod;
y=(y*y)%mod;
b=b/2;
}
return x;
}
ll C(ll n,ll r)
{
if(n==r)
return 1;
ll i,x=1,y=1;
for(i=(r+1);i<=n;i++)
x=(x*i)%mod;
for(i=1;i<=(n-r);i++)
y=(y*i)%mod;
return (x*powmod(y,mod-2))%mod;
}
void pre()
{
ll i,j;
comb[0][0]=1;
for(i=1;i<=10;i++)
for(j=0;j<=i;j++)
comb[i][j]=C(i,j);
}
void makeNode(ll node,ll x)
{
ll k;
x%=mod;
lazy[node]=0;
for(k=0;k<=10;k++)
tree[node][k]=powmod(x,k);
}
void combine(ll node)
{
ll k;
for(k=0;k<=10;k++)
tree[node][k]=(tree[2*node+1][k]+tree[2*node+2][k])%mod;
}
void build(ll node,ll start,ll end)
{
if(start==end)
{
makeNode(node,a[start]);
return;
}
ll mid=start+(end-start)/2;
build(2*node+1,start,mid);
build(2*node+2,mid+1,end);
combine(node);
}
void updateNode(ll node,ll x)
{
ll i,j,s;
ll f[12];
x%=mod;
for(i=1;i<=10;i++)
{
s=0;
for(j=0;j<=i;j++)
s=(s+(((comb[i][i-j]*powmod(x,i-j))%mod)*tree[node][j])%mod)%mod;
f[i]=s;
}
for(i=1;i<=10;i++)
tree[node][i]=f[i];
}
void updateLazy(ll node,ll start,ll end)
{
if(!lazy[node])
return;
updateNode(node,lazy[node]);
if(start!=end)
{
lazy[2*node+1]+=lazy[node];
lazy[2*node+2]+=lazy[node];
}
lazy[node]=0;
}
void pointUpdate(ll node,ll start,ll end,ll i,ll x)
{
updateLazy(node,start,end);
if(start==end)
{
makeNode(node,tree[node][1]+x);
return;
}
ll mid=start+(end-start)/2;
if(i<=mid)
{
pointUpdate(2*node+1,start,mid,i,x);
updateLazy(2*node+2,mid+1,end);
}
else
{
pointUpdate(2*node+2,mid+1,end,i,x);
updateLazy(2*node+1,start,mid);
}
combine(node);
}
void rangeUpdate(ll node,ll start,ll end,ll l,ll r,ll x)
{
updateLazy(node,start,end);
if(start>=l&&end<=r)
{
updateNode(node,x);
if(start!=end)
{
lazy[2*node+1]+=x;
lazy[2*node+2]+=x;
}
return;
}
ll mid=start+(end-start)/2;
if(l>mid)
{
rangeUpdate(2*node+2,mid+1,end,l,r,x);
updateLazy(2*node+1,start,mid);
}
else if(r<=mid)
{
rangeUpdate(2*node+1,start,mid,l,r,x);
updateLazy(2*node+2,mid+1,end);
}
else
{
rangeUpdate(2*node+1,start,mid,l,r,x);
rangeUpdate(2*node+2,mid+1,end,l,r,x);
}
combine(node);
}
ll query(ll node,ll start,ll end,ll l,ll r,ll k)
{
updateLazy(node,start,end);
if(start>=l&&end<=r)
return tree[node][k];
ll mid=start+(end-start)/2;
if(l>mid)
return query(2*node+2,mid+1,end,l,r,k);
else if(r<=mid)
return query(2*node+1,start,mid,l,r,k);
else
return (query(2*node+1,start,mid,l,r,k)
+query(2*node+2,mid+1,end,l,r,k))%mod;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
#ifndef ONLINE_JUDGE
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
#endif
ll t,q,i,n,c,l,r,k;
pre();
scanf("%lld",&t);
while(t--)
{
memset(tree,0,sizeof(tree));
memset(lazy,0,sizeof(lazy));
scanf("%lld",&n);
for(i=0;i<n;i++)
scanf("%lld",&a[i]);
build(0,0,n-1);
scanf("%lld",&q);
while(q--)
{
scanf("%lld",&c);
if(c==1)
{
//pointUpdate
scanf("%lld%lld",&i,&k);
pointUpdate(0,0,n-1,i-1,k);
}
else if(c==2)
{
//rangeUpdate
scanf("%lld%lld%lld",&l,&r,&k);
rangeUpdate(0,0,n-1,l-1,r-1,k);
}
else
{
//query
scanf("%lld%lld%lld",&l,&r,&k);
printf("%lld\n",query(0,0,n-1,l-1,r-1,k));
}
}
}
return 0;
}Second solution
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define fr freopen("in.txt","r",stdin)
#define rep(i,n) for(int i=0;i<n;i++)
#define frep(i,n) for(int i=1;i<=n;i++)
ll a[100011];
const ll mod = 1e9+7;
ll bpow(ll x,ll n) {
ll ans = 1;
while(n>0) {
if(n&1) ans*=x;
x*=x;
ans%=mod;
x%=mod;
n/=2;
}
return ans;
}
ll lazy[400011];
ll tree[400011][11];
ll lazyPower[11];
ll C[11][11];
struct node{
int l,r,id;
node() {
}
node(int _l,int _r,int _id) {
l = _l;
r = _r;
id = _id;
lazy_update();
}
node left() {
return node(l,(l+r)/2,2*id);
}
node right() {
return node((l+r)/2+1,r,2*id+1);
}
void lazy_update() {
if(lazy[id]==0) return;
lazyPower[0] = 1;
for(int j=1;j<11;j++) {
lazyPower[j] = lazy[id] * lazyPower[j-1];
lazyPower[j] %= mod;
}
for(int j=10;j>=1;j--) {
for(int k=0;k<j;k++) {
ll toAdd = tree[id][k];
toAdd*=lazyPower[j-k];
toAdd%=mod;
toAdd*=C[j][k];
toAdd%=mod;
tree[id][j]+=toAdd;
tree[id][j]%=mod;
}
}
if(l!=r) {
lazy[2*id]+=lazy[id];
lazy[2*id+1]+=lazy[id];
lazy[2*id]%=mod;
lazy[2*id+1]%=mod;
}
lazy[id] = 0;
}
void update(int s,int e,int val) {
if(r<s or e<l) return;
if(s<=l and r<=e) {
lazy[id]+=val;
lazy[id]%=mod;
lazy_update();
return;
}
left().update(s,e,val);
right().update(s,e,val);
rep(j,11) {
tree[id][j] = (tree[2*id][j]+tree[2*id+1][j])%mod;
}
}
ll query(int s,int e,int p) {
if(r<s or e<l) return 0;
if(s<=l and r<=e) {
return tree[id][p];
}
return (left().query(s,e,p)+right().query(s,e,p))%mod;
}
void build() {
if(l==r) {
rep(j,11) {
tree[id][j] = bpow(a[l],j);
}
return;
}
left().build();
right().build();
rep(j,11) {
tree[id][j] = (tree[2*id][j]+tree[2*id+1][j])%mod;
}
}
};
int main() {
C[0][0] = 1;
for(int i=1;i<=10;i++){
C[i][0] = 1;
for(int j=1;j<=i;j++) {
C[i][j] = C[i-1][j] + C[i-1][j-1];
C[i][j] %= mod;
}
}
int T;
cin >> T;
while(T--) {
int N;
cin >> N;
frep(i,N) {
cin >> a[i];
}
node stree(1,N,1);
stree.build();
int Q;
cin >> Q;
ll t,l,r,k;
while(Q--) {
cin >> t;
if(t==1) {
cin >> l >> k;
stree.update(l,l,k);
}
else if(t==2) {
cin >> l >> r >> k;
stree.update(l,r,k);
} else{
cin >> l >> r >> k;
cout << stree.query(l,r,k) << "\n";
}
}
}
}
0 Comments