如何做网站源码,网站建设相关知识,商业网站建立,如何仿做别人的网站士兵杀敌#xff08;四#xff09; 时间限制#xff1a;2000 ms | 内存限制#xff1a;65535 KB难度#xff1a;5描述南将军麾下有百万精兵#xff0c;现已知共有M个士兵#xff0c;编号为1~M#xff0c;每次有任务的时候#xff0c;总会有一批编号连在一起人请战四 时间限制2000 ms | 内存限制65535 KB 难度5 描述 南将军麾下有百万精兵现已知共有M个士兵编号为1~M每次有任务的时候总会有一批编号连在一起人请战编号相近的人经常在一块相互之间比较熟悉最终他们获得的军功也将会平分到每个人身上这样有时候计算他们中的哪一个人到底有多少军功就是一个比较困难的事情军师小工的任务就是在南将军询问他某个人的军功的时候快速的报出此人的军功请你编写一个程序来帮助小工吧。 假设起始时所有人的军功都是0. 输入只有一组测试数据。每一行是两个整数T和M表示共有T条指令M个士兵。1T,M1000000)随后的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 /* 功能Function Description: NYOJ-123 士兵杀敌四------树桩数组--插线问点2 开发环境Environment: DEV C 4.9.9.13 技术特点Technique:4 版本Version:5 作者Author: 可笑痴狂6 日期Date: 201208077 备注Notes:8 */9
10 // 代码一----树状数组插线问点
11 #includestdio.h
12 #includestring.h
13 int a[1000001];
14 int M;
15
16 int lowbit(int i)
17 {
18 return i(-i);
19 }
20
21 void update(int i,int num)
22 {
23 while(iM)
24 {
25 a[i]num;
26 ilowbit(i);
27 }
28 }
29
30 int getsum(int i)
31 {
32 int sum0;
33 while(i0)
34 {
35 suma[i];
36 i-lowbit(i);
37 }
38 return sum;
39 }
40
41 int main()
42 {
43 int T,st,end,k,i;
44 char cmd[10];
45 scanf(%d%d,T,M);
46 for(i0;iT;i)
47 {
48 scanf(%s,cmd);
49 if(cmd[0]A)
50 {
51 scanf(%d%d%d,st,end,k);
52 update(st,k);
53 update(end1,-k);
54 }
55 else
56 {
57 scanf(%d,k);
58 printf(%d\n,getsum(k)); //输出第k个人的军工
59 }
60 }
61 return 0;
62 } 1 //代码二2 //-----线段树(超时了----应该是代码写的大材小用了本题只用查询一个点3 //自己写的插入函数可以把线段都更新了适用于查询任意区间的军工总和把查询函数稍加改进就能查线段了)4 #includestdio.h5 #includemalloc.h6 7 struct node8 {9 int lc,rc;
10 int sum;
11 }*tree;
12
13 void build(int s,int t,int T)
14 {
15 int mid(st)1;
16 tree[T].lcs;
17 tree[T].rct;
18 tree[T].sum0;
19 if(st)
20 return ;
21 build(s,mid,T1);
22 build(mid1,t,(T1)|1);
23 }
24
25 void insert(int s,int t,int add,int T)
26 {
27 if(tree[T].lct||tree[T].rcs)
28 return ;
29 else if(stree[T].lcttree[T].rc)
30 tree[T].sumadd*(t-tree[T].lc1);
31 else if(stree[T].lcttree[T].rc)
32 tree[T].sumadd*(t-s1);
33 else if(stree[T].lcttree[T].rc)
34 tree[T].sumadd*(tree[T].rc-s1);
35 else
36 tree[T].sumadd*(tree[T].rc-tree[T].lc1);
37 if(tree[T].lctree[T].rc)
38 return ;
39 insert(s,t,add,T1);
40 insert(s,t,add,(T1)|1);
41 }
42
43 int qurry(int k,int T)
44 {
45 int mid(tree[T].lctree[T].rc)1;
46 if(ktree[T].lc||ktree[T].rc) //不在此范围内直接跳出
47 return 0;
48 if(tree[T].lctree[T].rc)
49 return tree[T].sum;
50 if(kmid)
51 return qurry(k,T1);
52 else
53 return qurry(k,(T1)|1);
54 }
55
56 int main()
57 {
58 int T,st,end,k,i,M;
59 char cmd[10];
60 scanf(%d%d,T,M);
61 tree(struct node *)malloc(M*3*sizeof(struct node));
62 build(1,M,1);
63 for(i0;iT;i)
64 {
65 scanf(%s,cmd);
66 if(cmd[0]A)
67 {
68 scanf(%d%d%d,st,end,k);
69 insert(st,end,k,1);
70 }
71 else
72 {
73 scanf(%d,k);
74 printf(%d\n,qurry(k,1)); //输出第k个人的军工
75 }
76 }
77 return 0;
78 }
