In this HackerEarth Super Power of 2s problem, Maggu loves to create problems involving queries. This time ,he has created one for you.
Given an array containing n elements and maggu asked you two types of queries.
type 0 : l r
type 1 : l r
HackerEarth Super Power Of 2s problem solution.
#include<bits/stdc++.h>
using namespace std;
#define scan(a) scanf("%d",&a)
#define scanll(a) scanf("%lld",&a)
#define print(a) printf("%d",a)
#define printll(a) printf("%lldn",a)
#define FOR(i,a,n) for(int i=a;i<n;i++)
#define VI vector<int>
#define VLL vector<long long >
#define ll long long
#define MOD 1000000007
#define MAX 200001
VLL arr,PW;
// power calculation
void pre_process(int n){
PW.resize(n+1);
PW[0]=1;
int i;
FOR(i,1,n+1){
PW[i]=(2*PW[i-1])%MOD;
}
FOR(i,1,n+1){
PW[i]=(PW[i]+PW[i-1])%MOD;
}
}
ll st[4*MAX]; // build auto
ll A[4*MAX];
bool F[4*MAX];
void adjust(int idx,int ss,int se){
st[idx]=(st[idx]+((A[idx]%MOD)*((PW[se-ss])%MOD))%MOD)%MOD;
int mid=(ss+se)>>1;
if(ss!=se){
A[2*idx+1]=(A[2*idx+1]+A[idx])%MOD;
A[2*idx+2]=(A[2*idx+2]+((A[idx]%MOD)*(((PW[mid-ss+1]-PW[mid-ss])%MOD+MOD)%MOD))%MOD)%MOD;
F[2*idx+1]=F[2*idx+2]=true;
}
F[idx]=0;
A[idx]=0;
return ;
}
void update(int idx,int ss,int se,int l,int r){
if(F[idx])adjust(idx,ss,se);
if(l>se||r<ss) return ;
if(l<=ss&&se<=r){
st[idx]=(st[idx]%MOD+((PW[se-l+1]-PW[ss-l])%MOD+MOD)%MOD)%MOD;
if(ss!=se){
int mid=(ss+se)>>1;
A[2*idx+1]=(A[2*idx+1]+((PW[ss-l+1]-PW[ss-l])%MOD+MOD)%MOD)%MOD;
A[2*idx+2]=(A[2*idx+2]+((PW[mid-l+2]-PW[mid+1-l])%MOD+MOD)%MOD)%MOD;
F[2*idx+1]=F[2*idx+2]=true;
}
return ;
}
int mid=(ss+se)>>1;
update(2*idx+1,ss,mid,l,r);
update(2*idx+2,mid+1,se,l,r);
st[idx]=(st[2*idx+1]+st[2*idx+2])%MOD;
}
ll query(int idx,int ss,int se,int l,int r){
if(F[idx]) adjust(idx,ss,se);
if(l>se||r<ss) return 0;
if(l<=ss&&se<=r) return st[idx]%MOD;
int mid=(ss+se)>>1;
ll L=query(2*idx+1,ss,mid,l,r);
ll R=query(2*idx+2,mid+1,se,l,r);
return (L+R)%MOD;
}
int main(){
int n;
scan(n);
pre_process(n);
arr.resize(n+1);
int i;
FOR(i,1,n+1){
ll x;
scanll(x);
arr[i]=(x+arr[i-1])%MOD;
}
int q;
scan(q);
while(q--){
int c,l,r;
scan(c);
scan(l);l--;
scan(r);r--;
if(!c){
update(0,0,n-1,l,r);
}else{
ll ans1=query(0,0,n-1,l,r)%MOD;
ll ans2=((arr[r+1]-arr[l])%MOD+MOD)%MOD;
ans1=(ans1+ans2)%MOD;
printll(ans1);
}
}
return 0;
}
Second solution
#include <bits/stdc++.h>
#define M 1000000007
int A[200001];
int tree[700005];
int lazy[700005];
bool flag[700005];
int p2[200001];
int dp[200001];
using namespace std;
inline void fi(int *a)
{
register char c=0;
while (c<33) c=getchar_unlocked();
*a=0;
int tmp = 0;
while (c>33)
{
if ( c == 45 ) tmp = 1;
else *a=*a*10+c-'0';
c=getchar_unlocked();
}
if ( tmp == 1 ) *a = 0-(*a);
}
void pre()
{
p2[0] = 1;
for ( int i = 1; i <= 200000; i++ ) {
p2[i] = p2[i-1]*2;
if ( p2[i] >= M ) p2[i] -= M;
}
return;
}
void build(int node, int left, int right)
{
if ( left > right ) return;
if ( left == right ) {
tree[node] = A[left];
return;
}
int mid = (left+right)>>1;
build(node<<1, left, mid);
build((node<<1)|1, mid+1, right);
tree[node] = (tree[node<<1] + tree[(node<<1)|1]);
if ( tree[node] >= M ) tree[node] -= M;
}
void pushdown(int node, int left, int right)
{
int mid = (left+right)>>1;
if ( flag[node] ) {
int val = (p2[right-left+1]-1);
if ( val < 0 ) val += M;
val = ((long long)val*(long long)lazy[node])%M;
tree[node] = (tree[node]+val);
if ( tree[node] >= M ) tree[node] -= M;
if ( left != right ) {
lazy[node<<1] = (lazy[node<<1]+lazy[node]);
lazy[(node<<1)|1] = (lazy[(node<<1)|1]+((long long)p2[mid+1-left]*(long long)lazy[node])%M);
if ( lazy[node<<1] >= M ) lazy[node<<1] -= M;
if ( lazy[(node<<1)|1] >= M ) lazy[(node<<1)|1] -= M;
flag[node<<1] = flag[(node<<1)|1] = true;
}
lazy[node] = 0;
flag[node] = false;
}
return;
}
void update(int node, int left, int right, int i, int j)
{
pushdown(node, left, right);
if ( left > right|| left > j || right < i ) return;
int mid = (left+right)>>1;
if ( left >= i && right <= j ) {
int val1 = p2[left-i+1];
int val2 = (p2[right-left+1]-1);
if ( val2 < 0 ) val2 += M;
val1 = ((long long)val1*(long long)val2)%M;
tree[node] = (tree[node] + val1);
if ( tree[node] >= M ) tree[node] -= M;
if ( left != right ) {
lazy[node<<1] = (lazy[node<<1]+p2[left-i+1]);
lazy[(node<<1)|1] = (lazy[(node<<1)|1]+p2[mid+1-i+1]);
if ( lazy[node<<1] >= M ) lazy[node<<1] -= M;
if ( lazy[(node<<1)|1] >= M ) lazy[(node<<1)|1] -= M;
flag[node<<1] = flag[(node<<1)|1] = true;
}
return;
}
update(node<<1, left, mid, i, j);
update((node<<1)|1, mid+1, right, i, j);
tree[node] = (tree[node<<1] + tree[(node<<1)|1]);
if ( tree[node] >= M ) tree[node] -= M;
}
int query(int node, int left, int right, int i, int j)
{
pushdown(node, left, right);
if ( left > right || left > j || right < i ) return 0;
if ( left >= i && right <= j ) return tree[node];
int mid = (left+right)>>1;
int p = query(node<<1, left, mid, i, j) + query((node<<1)|1, mid+1, right, i, j);
if ( p >= M ) p -= M;
return p;
}
int main()
{
pre();
int n,q,type,x,y;
fi(&n);
bool ff = false;
for ( int i = 0; i < n; i++ ) {
fi(&A[i]);
if ( i != 0 ) dp[i] = dp[i-1] + A[i];
else dp[i] = A[i];
if ( dp[i] >= M ) dp[i] -= M;
}
build(1,0,n-1);
fi(&q);
while ( q-- ) {
fi(&type); fi(&x); fi(&y);
x--; y--;
if ( type == 0 ) {
update(1,0,n-1,x,y);
ff = true;
}
else {
if ( !ff ) {
int ans;
if ( x == 0 ) ans = dp[y];
else {
ans = dp[y]-dp[x-1];
if ( ans < 0 ) ans += M;
}
printf("%dn", ans);
}
else printf("%dn", query(1,0,n-1,x,y));
}
}
return 0;
}
