计祘客的一道线段树 一直超时 实在不会了 求解答

Question

地址：https://nanti.jisuanke.com/t/10927
这是我的代码，太菜了 实在不会，有没有大神给点思路，始终不知道该怎么优化

 #include<iostream>
#include<cstdio>
#include<map>
#include<cstring>
#include<string>
#include<stack>
#include<queue>
#include<algorithm>
#include<cmath>
#include<vector>

using namespace std;
#define LL long long
int lev[15];
int n,m,q;
struct node
{
    int l,r;
    int mexp;
    int level;
    node* lc;
    node* rc;
    vector<int>ve;
    node()
    {
        lc = rc = NULL;
        level = 1;
        mexp = 0;
    }
};
int GetLevel(int exp)
{
    for(int i = m;i>1;i--)
    {
        if(exp>=lev[i])
        {
        //  cout << "level" << i << endl;
            return i;
        }
    }
    return 1;
}
void Build(int l,int r,node* root)
{
    root->l = l;
    root->r = r;
    if(l>=r)
    {
        return;
    }
    int mid = (l+r)/2;
    root->lc = new node();
    root->rc = new node();
    Build(l,mid,root->lc);
    Build(mid+1,r,root->rc);
}

void PushDown(node* root)
{
    /*if(root->e!=0 && root->l!=root->r)
    {
        PushDown(root->lc,root->e);
        PushDown(root->rc,root->e);
        root->e = 0;
    }
    root->e = e;
    if(root->l!=root->r)
        root->mexp = max(root->lc->mexp,root->rc->mexp);
    int level = GetLevel(root->mexp);
    root->mexp += e*level;*/
    if(root->lc==NULL || root->rc==NULL)
    return;
    if(root->ve.size()!=0)
    {
        for(int i = 0;i<root->ve.size();i++)
        {
            root->lc->mexp += root->ve[i]*root->lc->level;
            root->lc->level = GetLevel(root->lc->mexp);
            root->rc->mexp += root->ve[i]*root->rc->level;
            root->rc->level = GetLevel(root->rc->mexp);
        }
        for(int i = 0;i<root->ve.size();i++)
        {
            root->lc->ve.push_back(root->ve[i]);
            root->rc->ve.push_back(root->ve[i]);
        }
        root->ve.clear();
    }

}
void PushUp(node* root)
{
    if(root->l!=root->r)
    {
        root->mexp = max(root->lc->mexp,root->rc->mexp);
        root->level = max(root->lc->level,root->rc->level);
    }
}
void Update(int l,int r,int e,node* root)
{
    if(root==NULL)
    return;
    if(l<=root->l && root->r<=r)
    {
        root->mexp += root->level*e;
        root->ve.push_back(e);
        root->level = GetLevel(root->mexp);
        return;
    }
    PushDown(root);
    int mid = (root->l+root->r)/2;
    if(l<=mid)
    {
        Update(l,r,e,root->lc);
    }
    if(r>mid)
    {
        Update(l,r,e,root->rc);
    }
    PushUp(root);
}
int query(int l,int r,node* root)
{
    if(l<=root->l && root->r<=r)
    {
        //cout << root->level << endl;
        return root->mexp;
    }
    PushDown(root);
    int mid = (root->l+root->r)/2;
    int a1,a2;
    a1 = a2 = 0;
    if(l<=mid)
    {
        a1 = query(l,r,root->lc);
    }
    if(r>mid)
    {
        a2 = query(l,r,root->rc);
    }
    PushUp(root);
    return max(a1,a2);
}
void Dele(node* root)
{
    if(root->lc == NULL && root->rc==NULL)
    {
        root->ve.clear();
        delete root;
        return;
    }
    Dele(root->lc);
    Dele(root->rc);
    root->ve.clear();
    delete root;
}
int main()
{
    int t;
    scanf("%d",&t);
    int _case = 0;
    while(t--)
    {
        node* root = new node();
        scanf("%d%d%d",&n,&m,&q);
        Build(1,n,root);
        for(int i = 2;i<=m;i++)
        {
            scanf("%d",&lev[i]);
        }
        char ch;
        printf("Case %d:\n",++_case);
        while(q--)
        {
            cin >> ch;
            int a,b,c;
            switch(ch)
            {
                case 'W':
                    scanf("%d%d%d",&a,&b,&c);
                    Update(a,b,c,root);
                    break;
                    case 'Q':
                        scanf("%d%d",&a,&b);
                        printf("%d\n",query(a,b,root));
                        break;
            }
            //cout << ch << endl;
        }
        printf("\n");
        Dele(root);
    }
    return 0;
}

Answer 1

http://tieba.baidu.com/p/4505398035