Fenwick Tree HackerEarth

Question

私はHackeEarthの次のような問題を解決するために、次のフェンウィックツリーの実装を行っています：Question

#include <iostream> 

#define MAX 1000000007 
using namespace std; 


long long int dp[500006]; 
long long int GCD[500006]; 

// Function to Calculate GCD 
int gcd(int u, int v){ 
    int shl = 0; 

    while (u && v && u!=v) { 
    bool eu = !(u & 1); 
    bool ev = !(v & 1); 

    if (eu && ev) { 
     ++shl; 
     u >>= 1; 
     v >>= 1; 
    } 
    else if (eu && !ev) u >>= 1; 
    else if (!eu && ev) v >>= 1; 
    else if (u>=v) u = (u-v)>>1; 
    else { 
     int tmp = u; 
     u = (v-u)>>1; 
     v = tmp; 
    } 
    } 

    return !u? v<<shl : u<<shl; 
} 

//Function to calculate Cumulative GCD 

long long int cumulativeGCD(int x){ 
    long long int sum = 0; 
    if(!dp[x]){ 
     for(int i=1;i<=x;i++){ 
      sum += gcd(i,x); 
     } 
     dp[x] = sum; 
     return sum; 
    } 
    else return dp[x]; 
} 

// Retrieve the SUM function 

long long int getSum(long long int BITree[], int index) 
{ 
    long long int sum = 0; // Iniialize result 

    // index in BITree[] is 1 more than the index in arr[] 
    index = index + 1; 

    // Traverse ancestors of BITree[index] 
    while (index>0) 
    { 
     // Add current element of BITree to sum 
     sum += BITree[index]; 

     // Move index to parent node in getSum View 
     index -= index & (-index); 
    } 
    return sum; 
} 

// Update BIT function 

void updateBIT(long long int BITree[], int n, int index, long long int val) 
{ 
    // index in BITree[] is 1 more than the index in arr[] 
    index = index + 1; 

    // Traverse all ancestors and add 'val' 
    while (index <= n) 
    { 
     // Add 'val' to current node of BI Tree 
     if(BITree[index]>MAX) 
     BITree[index] = (BITree[index] + val)%MAX; 
     else BITree[index] += val; 


     // Update index to that of parent in update View 
     index += index & (-index); 
    } 
} 

// Construct BIT function 
long long int *constructBIT(int arr[], int size){ 
    long long int *BITree = new long long int[size+1](); 
    for (int i=0; i<size; i++) 
     updateBIT(BITree, size, i, GCD[i]); 

    return BITree; 
} 

int main() 
{ 
    int size,queries,index,value,start,end; 
    char type; 
    scanf("%d",&size); 
    int *arr= new int[size]; 
    for(int i=0;i<size;i++){ 
     scanf("%d",&arr[i]); 
     GCD[i] = cumulativeGCD(arr[i]); 
    } 
    long long int *BIT = constructBIT(arr,size); 
    scanf("%d",&queries); 
    while(queries--){ 
     cin>>type; 
     if(type=='C'){ 
      scanf("%d %d",&start,&end); 
      printf("%lld\n",getSum(BIT,end-1) - getSum(BIT,start-2)); 
     } 
     if(type=='U'){ 
      scanf("%d %d",&index,&value); 
      long long int diff = cumulativeGCD(value)-cumulativeGCD(arr[index-1]); 
      updateBIT(BIT,size,index-1,diff); 
     } 
    } 
    return 0; 
} 

私の解決策は、10回のテストケースのうち7回の制限時間を超えています。私はこのコードをさらに最適化することができません。どのようにすれば、テストケースごとに1秒未満で実行できるようにするには、どうすればこれを最適化できますか？どうもありがとうございました ！

Answer 1

あなたが解決している問題を指し示すリンクを提供し、シナリオをよりよく理解し、提案することができます。

if(BITree[index]>MAX) 
    BITree[index] = (BITree[index] + val)%MAX; 
    else BITree[index] += val; 

を削除し、BITree [インデックス] +ヴァル>をチェックしていないよう

BITree[index] = (BITree[index] + val) % MAX; 

と交換

typedef long long ll; 

ll gcd(ll a,ll b){ 
    if(!b) 
     return a; 
    else return gcd(b,a%b); 
} 

：しかし、GCD（）関数は、のように変形することができますMAX