HackerEarth Super Power Of 2s problem solution

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

coding problems solutions