hiho1077 : RMQ问题再临-线段树


题目链接
hihoCoder
http://hihocoder.com/problemset/problem/1077

思路和提示一致。但WA,求指点。

include <iostream>

include <stdlib.h>

using namespace std;

struct node
{
    node *father;
    node *leftchild;
    node *rightchild;
    int leftbound;
    int rightbound;
    int minvalue;
    node(){ father = leftchild = rightchild = NULL; leftbound = rightbound = 0; minvalue = 10000; }
};

int mymin(int a, int b)
{
    return (a < b ? a : b);
}
int myquery(node *curnode, int left, int right)
{
    if (left == curnode->leftbound && right == curnode->rightbound)
    {
        return curnode->minvalue;
    }
    int mid = (curnode->leftbound + curnode->rightbound) / 2;
    if (right <= mid)
    {
        return myquery(curnode->leftchild, left, right);
    }
    if (left > mid)
    {
        return myquery(curnode->rightchild, left, right);
    }
    return mymin(myquery(curnode->leftchild, left, mid), myquery(curnode->rightchild, mid + 1, right));
}
node *leaves[1000001];
node* buildtree(int *weight,int leftbound,int rightbound)
{
    node *tempnode = new node;
    if (leftbound == rightbound)
    {
        
        tempnode->leftbound = leftbound;
        tempnode->rightbound = rightbound;
        tempnode->minvalue = weight[leftbound];
        leaves[leftbound] = tempnode;
    }
    else
    {
        //node *tempnode = new node;
        tempnode->leftbound = leftbound;
        tempnode->rightbound = rightbound;
        tempnode->leftchild = buildtree(weight, leftbound, (leftbound + rightbound) / 2);
        tempnode->rightchild = buildtree(weight, (leftbound + rightbound) / 2 + 1, rightbound);
        tempnode->leftchild->father = tempnode;
        tempnode->rightchild->father = tempnode;
        tempnode->minvalue = mymin(tempnode->leftchild->minvalue, tempnode->rightchild->minvalue);
    }
    return tempnode;
}
void change(node *curnode, int new_weight)
{
    if (curnode == NULL)
        return;
    if (curnode->minvalue > new_weight)
    {
        curnode->minvalue = new_weight;
        change(curnode->father, new_weight);
    }
}
int main()
{
    int n;
    scanf("%d", &n);
    //cin >> n;
    int *weight = new int[n + 1];
    for (int i = 1; i <= n; i++)
        scanf("%d", &weight[i]);
        //cin >> weight[i];
    node *head = buildtree(weight, 1, n);
    head->father = NULL;
    delete[] weight;
    int q;
    scanf("%d", &q);
    //cin >> q;
    for (int k = 0; k < q; k++)
    {
        int op;
        scanf("%d", &op);
        //cin >> op;
        if (op == 0)//query
        {
            int l, r;
            scanf("%d %d", &l, &r);
            //cin >> l >> r;
            int ans = myquery(head, l, r);
            printf("%d\n", ans);
            //cout << ans << endl;
        }
        else if (op == 1)//change
        {
            int position, new_weight;
            scanf("%d %d", &position, &new_weight);
            //cin >> position >> new_weight;
            leaves[position]->minvalue = new_weight;
            change(leaves[position]->father, new_weight);
        }
    }
    return 0;
}
已邀请:

谢宏伟NJU

赞同来自:


change的时候不要比较所给的newWeight是否小于当前值,直接替换为newWeight.

要回复问题请先登录注册