{%hackmd @fishhh/style %}

# TPR #21 P_i
###### tags: `競程題解`,`競程`
Timestamp ： 2022/11/26

題目：
> TPR 國的人民心中有一個共同的恐慌指數 k
> 若第 i 天的確診人數為 di，那麼在第 i 天就會有 pi 個人感到恐慌
> 而 pi 算法為： $d_i×k+d_{i-1}×(k−1)+...+d_{i−k+1}×1$（如果 i<k 那就只算到 d1）

範圍：
> $1\leq n \leq 2×10^5$
> $1\leq k \leq 2×10^4$
> $1\leq d_i \leq 10^5$

複雜度分析：
1. 如果硬幹 那將會是$O(n×k)$ 明顯爆掉 (15%)
2. 可以試著把它做後綴和，這樣就可以得到題目的要求(40%)
:::spoiler code

#include "iostream"
using namespace std;
#define int long long
int bc[200010]={},ary[200010]={};
signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int n,k;
    cin>>n>>k;
    for(int i=1;i<=n;i++){
        cin>>ary[i];
    }
    for(int i=n;i>=0;i--){
        bc[i]=bc[i+1]+ary[i];
    }
    for(int i=1;i<=n;i++){
        int sum=0;
        for(int j=i;j>i-k;j--){
            if(j<1){
                sum+=bc[1];
            }
            else sum+=bc[j];
        }
        sum-=k*bc[i+1];
        cout<<sum<<" ";
    }
}

:::
4. 再將後綴和做一次前綴和(AC!)
:::spoiler code

#include "iostream"
using namespace std;
#define int long long
int bc[200010]={},ary[200010]={},pre[20010]={};
signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int n,k;
    cin>>n>>k;
    for(int i=1;i<=n;i++){
        cin>>ary[i];
    }
    for(int i=n;i>=0;i--){
        bc[i]=bc[i+1]+ary[i];
    }
    for(int i=1;i<=n;i++){
        pre[i]=bc[i]+pre[i-1];
    }
    for(int i=1;i<=n;i++){
        int sum=0;
        for(int j=i;j>i-k;j--){
            if(j<1){
                sum+=bc[1];
            }
            else sum+=bc[j];
        }
        sum=pre[i]-pre[max((int)0,i-k)];
        if(i-k<0){
            sum+=abs(i-k)*bc[1];
        }
        sum-=k*bc[i+1];
        cout<<sum<<" ";
    }
}

:::