方法为更好的解决方案 - 中位数

Question

这里的总和是问题Spoj-WEIRDFN

问题：

让我们定义：

F[1] = 1 
F[i] = (a*M[i] + b*i + c)%1000000007 for i > 1 

其中M[i]是由于阵列{F[1],F[2],..,F[i-1]} 的中位数a，b，c和n，计算总和F[1] + F[2] + .. + F[n]。

约束：

0 <= a,b,c < 1000000007 
1 <= n <= 200000 

我想出了一个解决方案，它是不那么有效

我的解决方案:: -

#include <bits/stdc++.h> 
using namespace std; 
#define ll long long int 
#define mod 1000000007 
int main() { 
    // your code goes here 
    int t; 
    scanf("%d",&t); 
    while(t--) 
    { 
     ll a,b,c,sum=0; 
     int n; 
     scanf("%lld%lld%lld%d",&a,&b,&c,&n); 
     ll f[n+1]; 
     f[1]=1; 
     f[0]=0; 
     for(int i=2;i<=n;i++) 
     { 
      ll temp; 
      sort(&f[1],&f[i]); 
      temp=f[i/2]; 
      f[i]=((a*(temp)%mod)+((b*i)%mod)+(c%mod))%mod; 
      sum+=f[i]; 
     } 
     printf("%lld\n",sum+f[1]); 
    } 
    return 0; 
} 

能人给我提示为更好的算法和数据结构，这个任务

Answer 1

对于每个测试用例，你可以保持binary search tree，这样你可以找到n个元素的中位数O(log n) time，而你只需要O（log n）的时间增加树中的新元素。因此，我们有一个O（T * nlogn）算法，其中T是测试用例的数量，n是元素的数量，它应该足以通过。