0

我试图解决一个非常基本的问题，它只涉及 Range Minimum Query 的实现。问题的链接是

https://www.hackerearth.com/practice/data-structures/advanced-data-structures/segment-trees/tutorial/

但是我超过了时间限制。请有人帮助调试我的代码。

#include <bits/stdc++.h>
#define inf 1000000000000000000
using namespace std;

vector<long long> segTree(2000005 , 0);
void createTree(vector<long long> v);
void createTreeUtil(vector<long long> v , int s,int e , int pos);
void updateTree(int x , int value , int n);
void updateTreeUtil(int s , int e , int pos , int x , int value);
long long getMinUtil(int s , int e , int pos , int srange , int erange);

long long getMin(int s , int e , int n);
int main(){
    int n,q;
    cin >> n >> q;

    vector<long long> v(n);
    for(int i=0;i<n;++i) cin >> v[i];
    //cout << "yes" << endl;
    createTree(v);
    /*cout << "seg tree is " ;
    for(int i=0;i<segTree.size();++i) cout << segTree[i] << " ";
    cout << endl;*/
    //cout << "yes" << endl;
    while(q--){
        int x , y;
        char c;
        cin >> c >> x >> y;
        if(c == 'u'){
            --x; 
            updateTree(x , y , n);
        }
        else{
            --x , --y; 
            cout << getMin(x , y , n) << endl;
        }
    }


    return 0;
}

void createTree(vector<long long> v){

    int l = v.size();
    createTreeUtil(v , 0 , l-1 , 0);
}

void createTreeUtil(vector<long long> v , int s,int e , int pos){
    if(s>e) return;
    int left = 2*pos+1 , right = 2*pos+2;
    if(s==e){
        segTree[pos] = v[s];
        return;
    }
    int mid = (s+e)/2;
    createTreeUtil(v , s , mid , left);
    createTreeUtil(v , mid+1 , e , right);
    segTree[pos] = min(segTree[left] , segTree[right]);

}

void updateTree(int x , int value , int n){

    updateTreeUtil(0 , n-1 , 0 , x , value);

}

void updateTreeUtil(int s , int e , int pos , int x , int value){
    if(s == e){

        if(s == x) segTree[s] = value;
        return;
    }
    if(x<s || x>e) return;
    int left = 2*pos+1 , right= 2*pos+2 , mid = (s+e)/2;
    updateTreeUtil(s , mid , left , x , value);
    updateTreeUtil(mid+1 , e , right , x , value);
    segTree[pos] = min(segTree[left] , segTree[right]);
}

long long getMin(int s , int e , int n){

    return getMinUtil(0 , n-1 , 0 , s , e);

}

long long getMinUtil(int s , int e , int pos , int srange , int erange){
    int mid = (s+e)/2 , left = 2*pos+1 , right = 2*pos+2;
    if(s > erange || e < srange) return inf;
    if(s >= srange && e <= erange) return segTree[pos];
    return min(getMinUtil(s , mid , left , srange , erange) ,               getMinUtil(mid+1 , e , right , srange , erange));
}

提前致谢

4

1 回答 1

0

由于 C++ 按值传递参数，因此超出了时间限制。

这意味着每次调用 createTreeUtil 时，都会创建一个包含 100,000 个元素的输入向量的新副本。

尝试改变：

void createTree(vector<long long> v);
void createTreeUtil(vector<long long> v , int s,int e , int pos);

使用参考：

void createTree(vector<long long> &v);
void createTreeUtil(vector<long long> &v , int s,int e , int pos);

（您需要在声明函数的文件顶部和实际定义函数的位置更改这些签名。）

于 2017-08-04T08:32:16.757 回答