士兵殺敵（四）

時間限制：2000?ms ?|? 內(nèi)存限制：65535?KB 難度：5 描述

南將軍麾下有百萬精兵，現(xiàn)已知共有M個士兵，編號為1~M，每次有任務(wù)的時候，總會有一批編號連在一起人請戰(zhàn)（編號相近的人經(jīng)常在一塊，相互之間比較熟悉），最終他們獲得的軍功，也將會平分到每個人身上，這樣，有時候，計(jì)算他們中的哪一個人到底有多少軍功就是一個比較困難的事情，軍師小工的任務(wù)就是在南將軍詢問他某個人的軍功的時候，快速的報出此人的軍功，請你編寫一個程序來幫助小工吧。

假設(shè)起始時所有人的軍功都是0.

輸入

只有一組測試數(shù)據(jù)。
每一行是兩個整數(shù)T和M表示共有T條指令，M個士兵。（1<=T,M<=1000000)
隨后的T行，每行是一個指令。
指令分為兩種：
一種形如
ADD 100 500 55 表示，第100個人到第500個人請戰(zhàn)，最終每人平均獲得了55軍功，每次每人獲得的軍功數(shù)不會超過100，不會低于-100。
第二種形如：
QUERY 300 表示南將軍在詢問第300個人的軍功是多少。

輸出

對于每次查詢輸出此人的軍功，每個查詢的輸出占一行。

樣例輸入

4 10 ADD 1 3 10 QUERY 3 ADD 2 6 50 QUERY 3

樣例輸出

10 60

樹狀數(shù)組！

插線問點(diǎn)！

AC碼：

#include<stdio.h> int n,num; int sum[1000010]; int LowBit(int i) {return i&(-i); } void Plus(int i,int value) {while(i>0){sum[i]+=value;i-=LowBit(i);} } int Get(int i) {int result=0;while(i<=num){result+=sum[i];i+=LowBit(i);}return result; } int main() {int i,a,b,value;char str[6];scanf("%d%d",&n,&num);for(i=1;i<=n;i++){scanf("%s",str);if(str[0]=='A'){scanf("%d%d%d",&a,&b,&value);Plus(a-1,-value);Plus(b,value);}else{scanf("%d",&a);printf("%d\n",Get(a));}}return 0; }

與50位技術(shù)專家面對面20年技術(shù)見證，附贈技術(shù)全景圖

總結(jié)

以上是生活随笔為你收集整理的NYOJ 123 士兵杀敌(四)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。