线段树，希望能有高人指点。
#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;}