和普通的線段樹不同的是，查詢x~y的話，給出的答案是第一個值的一倍加上第二個值的兩倍一直到第n個值的n倍。
思路的話，就是關于query和pushup的方法。用一個新的變量sum記錄一下這個區間里面按照答案給出的方式的值，比如說，這個節點的區間是1~3，那么這個節點的sum值就是(1*val[1]+2*val[2]+3*val[3])。那么對于pushup操作，當前這個節點的sum值是左邊的sum值+左邊的區間長度*右邊的c值（c值代表的是這個區間的所有元素的和）+右邊的sum值。這樣的話就相當于右邊的sum升高了需要的高度，就滿足題意了。
另外關于query也是類似，要返回時，加上(l-ql)倍的c[o]的值就行了，這樣就相當于右邊的sum升高了(l-ql)的高度了。如果不能理解，可以手動模擬一下試試。
但是這題WA了好多次，，因為我現在才知道原來uva的long long得用lld，QAQ。。。
具體見代碼：
?
1 #include <stdio.h> 2 #include <algorithm> 3 #include <string.h> 4 #define t_mid (l+r>>1) 5 #define ls o<<1 6 #define rs o<<1 | 1 7 #define lson ls,l,t_mid 8 #define rson rs,t_mid+1,r 9 using namespace std; 10 typedef long long ll; 11 12 const int N = 100000 + 5; 13 ll c[N<<2],sum[N<<2],add[N<<2]; 14 15 void pushup(int o,int len){c[o]=c[ls]+c[rs];sum[o]=sum[ls]+c[rs]*len+sum[rs];} 16 17 void build(int o,int l,int r) 18 { 19 add[o]=0; 20 if(l==r) {c[o]=sum[o]=100;return;} 21 build(lson); 22 build(rson); 23 pushup(o,t_mid-l+1); 24 } 25 26 void pushdown(int o,int len) 27 { 28 if(add[o]) 29 { 30 int llen=(len-(len>>1)),rlen=(len>>1); 31 add[ls] += add[o]; 32 add[rs] += add[o]; 33 c[ls] += add[o]*llen; 34 c[rs] += add[o]*rlen; 35 sum[ls] += add[o]*(llen)*(llen+1)/2; 36 sum[rs] += add[o]*(rlen)*(rlen+1)/2; 37 add[o]=0; 38 } 39 } 40 41 void update(int o,int l,int r,int ql,int qr,int dt) 42 { 43 if(ql <= l && qr >= r) 44 { 45 add[o] += (ll)dt; 46 c[o] += (ll)dt*(r-l+1); 47 sum[o] += (ll)dt*(r-l+1)*(r-l+2)/2; 48 return; 49 } 50 pushdown(o,r-l+1); 51 if(ql <= t_mid) update(lson,ql,qr,dt); 52 if(qr >t_mid) update(rson,ql,qr,dt); 53 pushup(o,t_mid-l+1); 54 } 55 56 ll query(int o,int l,int r,int ql,int qr) 57 { 58 if(ql <= l && qr >= r) 59 { 60 return (l-ql)*c[o]+sum[o]; 61 } 62 pushdown(o,r-l+1); 63 ll res = 0; 64 if(ql <= t_mid) res += query(lson,ql,qr); 65 if(qr > t_mid) res += query(rson,ql,qr); 66 return res; 67 } 68 69 int main() 70 { 71 int T; 72 scanf("%d",&T); 73 for(int kase=1;kase<=T;kase++) 74 { 75 printf("Case %d:\n",kase); 76 int n,m; 77 scanf("%d%d",&n,&m); 78 build(1,1,n); 79 80 while(m--) 81 { 82 char s[10]; 83 scanf("%s",s); 84 if(s[0]=='c') 85 { 86 int x,y,dt; 87 scanf("%d%d%d",&x,&y,&dt); 88 update(1,1,n,x,y,dt); 89 } 90 else 91 { 92 int x,y; 93 scanf("%d%d",&x,&y); 94 printf("%lld\n",query(1,1,n,x,y)); 95 } 96 } 97 } 98 }
?
)
