# 线段树 – 有改动求解区间最值 – 忠诚 2

 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 int Update(Node *pNode) { if(pNode->nLeft == pNode->nRight || pNode->nMoney != 2147483647) { return pNode->nMoney; } else { return pNode->nMoney = min(Update(pNode->pLeft), Update(pNode->pRight)); } } void Change(Node *pNode, int x, int nValue) { pNode->nMoney = 2147483647; if(pNode->nLeft == x && x == pNode->nRight) { pNode->nMoney = nValue; } else { if(x <= (pNode->nLeft + pNode->nRight) / 2) { Change(pNode->pLeft, x, nValue); } else { Change(pNode->pRight, x, nValue); } } }

 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 #include #include using namespace std; struct Node { int nLeft, nRight; unsigned long long nMoney; Node *pLeft, *pRight; }; Node *pRoot; int N, M, nTmp, T, L, R, ans; vector pMoney; Node* Build(int l, int r); int Update(Node *pNode); void Change(Node *pNode, int x, int nValue); int Query(Node *pNode, int l, int r); int main() { ios::sync_with_stdio(false); cin >> N >> M; for(int i = 1; i <= N; i++) { cin >> nTmp; pMoney.push_back(nTmp); } pRoot = Build(1, N); Update(pRoot); for(int i = 1; i <= M; i++) { cin >> T >> L >> R; if(T == 1) { ans = 2147483647; cout << Query(pRoot, L, R) << " "; } else { Change(pRoot, L, R); Update(pRoot); } } cout << endl; return 0; } Node* Build(int l, int r) { Node *pNode = new Node(); if(l == r) { pNode->nMoney = pMoney[l - 1]; } else { pNode->nMoney = 2147483647; } pNode->nLeft = l; pNode->nRight = r; if(l == r) { return pNode; } int nMid = (l + r) / 2; pNode->pLeft = Build(l, nMid); pNode->pRight = Build(nMid + 1, r); return pNode; } int Update(Node *pNode) { if(pNode->nLeft == pNode->nRight || pNode->nMoney != 2147483647) { return pNode->nMoney; } else { return pNode->nMoney = min(Update(pNode->pLeft), Update(pNode->pRight)); } } void Change(Node *pNode, int x, int nValue) { pNode->nMoney = 2147483647; if(pNode->nLeft == x && x == pNode->nRight) { pNode->nMoney = nValue; } else { if(x <= (pNode->nLeft + pNode->nRight) / 2) { Change(pNode->pLeft, x, nValue); } else { Change(pNode->pRight, x, nValue); } } } int Query(Node *pNode, int l, int r) { if(pNode->nLeft == l && r == pNode->nRight) { return pNode->nMoney; } else { if(r <= (pNode->nLeft + pNode->nRight) / 2) { return Query(pNode->pLeft, l, r); } else if(l > (pNode->nLeft + pNode->nRight) / 2) { return Query(pNode->pRight, l, r); } else { int nMid = (pNode->nLeft + pNode->nRight) / 2; return min(Query(pNode->pLeft, l, nMid), Query(pNode->pRight, nMid + 1, r)); } } }