c++ - hihocoder#1034 毁灭者问题，提交总是WA

Question

有几个疑惑的地方，感觉自己用的线段树并没有节省时间，但那样也只是超时不应该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 <iostream>
#include <math.h>
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;
}