士兵杀敌(四)
时间限制:2000 ms | 内存限制:65535 KB
难度:5
- 描述
-
南将军麾下有百万精兵,现已知共有M个士兵,编号为1~M,每次有任务的时候,总会有一批编号连在一起人请战(编号相近的人经常在一块,相互之间比较熟悉),最终他们获得的军功,也将会平分到每个人身上,这样,有时候,计算他们中的哪一个人到底有多少军功就是一个比较困难的事情,军师小工的任务就是在南将军询问他某个人的军功的时候,快速的报出此人的军功,请你编写一个程序来帮助小工吧。
假设起始时所有人的军功都是0.
- 输入
- 只有一组测试数据。
每一行是两个整数T和M表示共有T条指令,M个士兵。(1<=T,M<=1000000)
随后的T行,每行是一个指令。
指令分为两种:
一种形如
ADD 100 500 55 表示,第100个人到第500个人请战,最终每人平均获得了55军功,每次每人获得的军功数不会超过100,不会低于-100。
第二种形如:
QUERY 300 表示南将军在询问第300个人的军功是多少。 - 输出
- 对于每次查询输出此人的军功,每个查询的输出占一行。
- 样例输入
-
4 10 ADD 1 3 10 QUERY 3 ADD 2 6 50 QUERY 3
- 样例输出
-
10 60
- 来源
- [张云聪]原创
- 上传者
- 张云聪
-
1 #include <stdio.h> 2 #include <string.h> 3 4 int c[1000010],n; 5 6 int lowbit(int n) 7 { 8 return n&(-n); 9 } 10 11 void add(int i,int t) 12 { 13 while(i<=n) 14 { 15 c[i]+=t; 16 i+=lowbit(i); 17 } 18 } 19 20 int sum(int n) 21 { 22 int s=0; 23 while(n>0) 24 { 25 s+=c[n]; 26 n-=lowbit(n); 27 } 28 return s; 29 } 30 31 int main() 32 { 33 int i,j,t1,t2,t,m; 34 char str[10]; 35 memset(c,0,sizeof(c)); 36 scanf("%d %d",&m,&n); 37 for(i=1;i<=m;i++) 38 { 39 scanf("%s",str); 40 if(str[0]=='A') 41 { 42 scanf("%d%d%d",&t1,&t2,&t); 43 add(t1,t); 44 add(t2+1,-t); 45 } 46 else 47 { 48 scanf("%d",&t); 49 printf("%d ",sum(t)); 50 } 51 } 52 return 0; 53 } 54 //树状数组--插线取点
关于插线问点,思路一看代码就能懂,就是把a点后面的值全加x,然后把b+1后面的值全减x,这样就相当于只给[a,b]区间内的值加了x。
Ps:关于树状数组,最重要的一点就是,一定要从1开始,不能从0开始,因为lowbit(0)=0,会出现死循环。