0

我有一个 Fenwick 树的以下实现来解决 HackeEarth 上的以下问题。

#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 秒内运行。非常感谢 ！

4

1 回答 1

0

提供指向您正在解决的问题的链接，以便我们更好地了解场景并为您提供建议。但是，gcd() 函数可以修改为：

typedef long long ll;

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

消除

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

并替换为

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

因为你没有检查 BITree[index] + val > MAX

于 2016-09-17T07:31:28.290 回答