一個非常暴力的常數優化

就是下面這一行

#pragma GCC optimize ("O3,unroll-loops")

可以做到什麼效果呢?在某些情況下可以讓O(n^2)硬解10^5的測資。

int a[100010];

for(int i=0;i<n;++i) cin>>a[i];

for(int i=0;i<q;++i){
    int l,r;
    cin>>l>>r;

    int ret=0;
    for(int j=l;j<r;++j){
        ret+=a[j];
    }
    cout<<ret<<"\n";
}

原本要用前綴和,變爆搜就會過。

發佈留言

發佈留言必須填寫的電子郵件地址不會公開。 必填欄位標示為 *