有几个疑惑的地方,感觉自己用的线段树并没有节省时间,但那样也只是超时不应该WA吧。
原题详见:http://hihocoder.com/problemset/problem/1034
时间限制:10000ms
单点时限:1000ms
内存限制:256MB
描述
在 Warcraft III 之冰封王座中,毁灭者是不死族打三本后期时的一个魔法飞行单位。
毁灭者的核心技能之一,叫做魔法吸收(Absorb Mana):
14054064004625.png
现在让我们来考虑下面的问题:
假设你拥有 n 个魔法单位,他们从左到有站在一行,编号从 1 到 n。 每个单位拥有三项属性:
si: 初始法力。
mi: 最大法力上限。
ri: 每秒中法力回复速度。
现在你操纵一个毁灭者,有 m 个操作,t l r,表示时刻 t,毁灭者对所有编号从 l 到 r 的单位,使用了魔法吸收。操作按照时间顺序给出,计算毁灭者一共吸收了多少法力。
输入
输入数据的第一行有一个整数 n(1 ≤ n ≤105) — 你的魔法单位的数目。
接下来的 n 行,每行有三个整数 si, mi, ri(0 ≤ si ≤ mi ≤ 105, 0 ≤ ri ≤ 105) 描述一个魔法单位。
接下来一行又一个整数 m(1 ≤ m ≤ 105), — 操作的数目。
接下来的 m 行,每行描述一个操作 t, l, r(0 ≤ t ≤ 109, 1 ≤ l ≤ r ≤ n),t 非降。
输出
输出一行一个整数表示毁灭者一共吸收了多少法力。
样例输入
5
0 10 1
0 12 1
0 20 1
0 12 1
0 10 1
2
5 1 5
19 1 5
样例输出
83
#include#include using namespace std; struct unit { int startMana, maxMana, rresSpeed; }; struct operation { int time, leftIndex, rightIndex; }; struct intervalTreeNode { int left, right; intervalTreeNode *leftNode,*rightNode; int sumMana; }; struct intervalTree { intervalTreeNode* root; }; intervalTreeNode* createIntervalTreeNode(intervalTreeNode* parent, unit* mUnits,bool isLeftNode) { intervalTreeNode *node = new intervalTreeNode; int middle = (int)ceil((parent->left + parent->right) / 2.0 ); if (isLeftNode) { node->left = parent->left; node->right = middle - 1; } else {//isRightNode node->left = middle; node->right = parent->right; } if (node->right == node->left) { //leaf node node->leftNode = NULL; node->rightNode = NULL; node->sumMana = mUnits[node->left - 1].startMana; } else { node->leftNode = createIntervalTreeNode(node,mUnits,true); node->rightNode = createIntervalTreeNode(node, mUnits,false); node->sumMana = node->leftNode->sumMana + node->rightNode->sumMana; } return node; } intervalTree* createIntervalTree(unit* mUnits, int unitsNum){ intervalTree *mTree = new intervalTree; intervalTreeNode* mRoot = new intervalTreeNode; mRoot->left = 1; mRoot->right = unitsNum; mRoot->leftNode = createIntervalTreeNode(mRoot, mUnits, true); mRoot->rightNode = createIntervalTreeNode(mRoot, mUnits, false); mRoot->sumMana = mRoot->leftNode->sumMana + mRoot->rightNode->sumMana; (*mTree).root = mRoot; return mTree; } void recoverMana(int time, unit* mUnits, intervalTreeNode* root) { intervalTreeNode* pNode = root; if (pNode->left == pNode->right) { pNode->sumMana = pNode->sumMana + time * mUnits[pNode->left - 1].rresSpeed; pNode->sumMana = pNode->sumMana >= mUnits[pNode->left - 1].maxMana ? mUnits[pNode->left - 1].maxMana : pNode->sumMana; return; } recoverMana(time, mUnits, pNode->leftNode); recoverMana(time, mUnits, pNode->rightNode); pNode->sumMana = pNode->leftNode->sumMana + pNode->rightNode->sumMana; } int obtainMana(intervalTreeNode* root,int leftIndex, int rightIndex) { int mana = 0, manaLeft = 0, manaRight = 0; intervalTreeNode* node = root; if (node->left == node->right) { mana += node->sumMana; node->sumMana = 0; return mana; } if(node->leftNode->right >= leftIndex) manaLeft = obtainMana(node->leftNode, leftIndex, rightIndex); if(node->rightNode->left <= rightIndex) manaRight = obtainMana(node->rightNode, leftIndex, rightIndex); mana = manaLeft + manaRight; node->sumMana = node->sumMana - manaLeft - manaRight; return mana; } int getMana(unit* mUnits, operation* mOperations, intervalTree* Tree, int operationNum) { int sumMana = 0; int time = 0; intervalTreeNode* node = Tree->root; for (int i = 0; i < operationNum; i++) { time = time ==0 ? mOperations[i].time : mOperations[i].time - mOperations[i-1].time; recoverMana(time, mUnits, node); sumMana += obtainMana(Tree->root, mOperations[i].leftIndex, mOperations[i].rightIndex); } return sumMana; } int main(int argv, char argc) { int unitsNum,operationNum; intervalTree* Tree = new intervalTree; cin >> unitsNum; unit *mUnits = new unit[unitsNum]; for (int i = 0; i < unitsNum; ++i) { cin >> mUnits[i].startMana >> mUnits[i].maxMana >> mUnits[i].rresSpeed; } Tree = createIntervalTree(mUnits,unitsNum); cin >> operationNum; operation *mOperations = new operation[operationNum]; for (int i = 0; i < operationNum; ++i) { cin >> mOperations[i].time >> mOperations[i].leftIndex >> mOperations[i].rightIndex; } cout << getMana(mUnits, mOperations, Tree, operationNum); delete mUnits, mOperations, Tree; return 0; }