线段树，希望能有高人指点。

C/C++ code

#include<iostream>#include<queue>using namespace std;inline int max(int a,int b){    return a>b?a:b;}struct Seg_tree{    int left,right;    int level;    int exp;    queue<int>q;    int calmid()    {        return (left+right)>>1;    }};Seg_tree tree[45];int arr[11];int k;void build(int left,int right,int idx) //建树{    tree[idx].left=left;    tree[idx].right=right;    tree[idx].exp=0;    tree[idx].level=1;    if(left==right)        return ;    int mid=tree[idx].calmid();    build(left,mid,idx*2);    build(mid+1,right,idx*2+1);}void update(int left,int right,int ei,int idx) //更新节点，先找到对应节点，在把ei放入该节点所定义的队列中。。{    if(tree[idx].left==left&&tree[idx].right==right)    {        tree[idx].q.push(ei);        return ;    }    while(!tree[idx].q.empty()) //如果需要更新的节点的祖先的队列里有值，这把该祖先节点的值向下推进。。    {        int t=tree[idx].q.front();        tree[idx*2].q.push(t);        tree[idx*2+1].q.push(t);        tree[idx].q.pop();    }    int mid=tree[idx].calmid();    if(right<=mid)        update(left,right,ei,idx*2);    else if(left>mid)        update(left,right,ei,idx*2+1);    else    {        update(left,mid,ei,idx*2);        update(mid+1,right,ei,idx*2+1);    }    tree[idx].exp=max(tree[idx*2].exp,tree[idx*2+1].exp);}int down(int idx) //对找到的节点进行处理。。向下推进到叶子节点，更新叶子节点的exp;对每个节点的父节点，返回其子节点的最大exp{    if(tree[idx].left==tree[idx].right)    {        while(!tree[idx].q.empty())        { //错误总是在这个地方。。当输入第二组样例时，到这个地方就会出错。。            int t=tree[idx].q.front();            tree[idx].q.pop();               tree[idx].exp+=t*tree[idx].level;            if(tree[idx].exp>arr[tree[idx].level]&&tree[idx].level<k)            tree[idx].level++;        }            return tree[idx].exp;    }    while(!tree[idx].q.empty())    {            int t=tree[idx].q.front();            tree[idx*2].q.push(t);            tree[idx*2+1].q.push(t);            tree[idx].q.pop();    }    tree[idx].exp= max(down(idx*2),down(idx*2+1));    return tree[idx].exp;}int question(int left,int right,int idx)//找到需要查询的节点。。返回down(idx);{    if(tree[idx].left==left&&tree[idx].right==right)    return down(idx);    while(!tree[idx].q.empty())    {        int t=tree[idx].q.front();        tree[idx*2].q.push(t);        tree[idx*2+1].q.push(t);        tree[idx].q.pop();    }    int mid=tree[idx].calmid();    if(right<=mid)        question(left,right,idx*2);    if(left>mid)        question(left,right,idx*2+1);    else    {        question(left,mid,idx*2);        question(mid+1,right,idx*2+1);    }    tree[idx].exp =max(tree[idx*2].exp,tree[idx*2+1].exp);    return tree[idx].exp;}int main(){    int T;    //cin>>T;    scanf("%d",&T);    arr[0]=0;    int j=1;    while(T--)    {        //cout<<"Case "<<j<<":"<<endl;        printf("Case %d:\n",j);        j++;        int N,w;        //cin>>N>>k>>w;        scanf("%d%d%d",&N,&k,&w);        int i;        for(i=1;i<k;++i)        {            //cin>>arr[i];            scanf("%d",&arr[i]);            arr[i]+=arr[i-1];        }        build(1,N,1);        char ch;        int a,b,c;        for(i=0;i<w;++i)        {            cin>>ch;            if(ch=='W')            {                //cin>>a>>b>>c;                scanf("%d%d%d",&a,&b,&c);                update(a,b,c,1);            }            if(ch=='Q')            {                //cin>>a>>b;                scanf("%d%d",&a,&b);                cout<<question(a,b,1)<<endl;            }        }        cout<<endl;    }    return 0;}

好久以前的东西了, 实在懒得看, 仅限于干ACM题的算法.