nyoj123_士兵杀敌（四）_树状数组_插线求点
士兵杀敌（四）
时间限制： 2000 ms | 内存限制：65535 KB
难度： 5
南将军麾下有百万精兵，现已知共有M个士兵，编号为1~M，每次有任务的时候，总会有一批编号连在一起人请战（编号相近的人经常在一块，相互之间比较熟悉），最终他们获得的军功，也将会平分到每个人身上，这样，有时候，计算他们中的哪一个人到底有多少军功就是一个比较困难的事情，军师小工的任务就是在南将军询问他某个人的军功的时候，快速的报出此人的军功，请你编写一个程序来帮助小工吧。
假设起始时所有人的军功都是0.
</dd> </dl>每一行是两个整数T和M表示共有T条指令，M个士兵。（1<=T,M<=1000000)
随后的T行，每行是一个指令。
指令分为两种：
一种形如
ADD 100 500 55 表示，第100个人到第500个人请战，最终每人平均获得了55军功，每次每人获得的军功数不会超过100，不会低于-100。
第二种形如：
QUERY 300 表示南将军在询问第300个人的军功是多少。 </dd> <dt> 输出 </dt> <dd> 对于每次查询输出此人的军功，每个查询的输出占一行。 </dd> <dt> 样例输入 </dt> <dd>
4 10 ADD 1 3 10 QUERY 3 ADD 2 6 50 QUERY 3</dd> <dt> 样例输出 </dt> <dd>
10 60</dd> <dt> 来源 </dt> <dd> [张云聪]原创 </dd> <dt> 上传者 </dt> <dd> 张云聪 </dd> </dl>
解题思路：前一个士兵杀敌（3）是插点求线的题，每次出现一个点，都要向start+lowbit()的方向更新，因为c[i]里面存的是从0到i的和。每次求区间（a,b）的时候要用前b项的和-前a项的和，就是sum(b)-sum(a);
而这个题是插线求点，出现一个线段(a,b)且区间上要加的为num时，，要向b-lowbit的方向更新（+num），再从a-1处向a-lowbit的方向更新（-num），求点的时候sum（i）是从i向后求，把后面+lowbit得到的位置的值都加上，因为之前当加区间的时候，把区间之前的值都减去了num，所以要再加回来。。。
代码：
#include <iostream> #include <cstdio> #include <cstring> using namespace std; int c[1000005]; int n;//士兵数 int m;//指令数 int lowbit(int x){ return x&(-x); } void update(int p,int q){ while(p>0){ c[p]+=q; p-=lowbit(p); } } int sum(int x){ int sum=0; while(x<=m){ sum+=c[x]; x+=lowbit(x); } return sum; } int main() { int a,b,num; char s[10]; scanf("%d %d",&n,&m); for(int i=0;i<n;i++){ scanf("%s",s); if(s[0]=='A'){ scanf("%d %d %d",&a,&b,&num); update(b,num); update(a-1,-1*num); }else{ scanf("%d",&a); int f=sum(a); printf("%d\n",f); } } return 0; }
投递华为等公司10个岗位 >
查看6道真题和解析