nyoj--116--士兵杀敌（二）

浅浅的花香味﹌ 2022-06-10 05:25 170阅读 0赞

## 士兵杀敌（二） ##

时间限制： 1000 ms  |  内存限制： 65535 KB

难度： 5

描述

南将军手下有N个士兵，分别编号1到N，这些士兵的杀敌数都是已知的。

小工是南将军手下的军师，南将军经常想知道第m号到第n号士兵的总杀敌数，请你帮助小工来回答南将军吧。

南将军的某次询问之后士兵i可能又杀敌q人，之后南将军再询问的时候，需要考虑到新增的杀敌数。

输入

只有一组测试数据 
第一行是两个整数N,M，其中N表示士兵的个数(1<N<1000000)，M表示指令的条数。(1<M<100000) 
随后的一行是N个整数，ai表示第i号士兵杀敌数目。(0<=ai<=100) 
随后的M行每行是一条指令，这条指令包含了一个字符串和两个整数，首先是一个字符串，如果是字符串QUERY则表示南将军进行了查询操作，后面的两个整数m,n，表示查询的起始与终止士兵编号；如果是字符串ADD则后面跟的两个整数I,A(1<=I<=N,1<=A<=100),表示第I个士兵新增杀敌数为A.

输出

对于每次查询，输出一个整数R表示第m号士兵到第n号士兵的总杀敌数，每组输出占一行

样例输入

5 6
    1 2 3 4 5
    QUERY 1 3
    ADD 1 2
    QUERY 1 3
    ADD 2 3
    QUERY 1 2
    QUERY 1 5

样例输出

6
    8
    8
    20

解题思路：

这题我是用线段树做的，主要用到了线段树的，建树，更新和查询的操作，在输入每个士兵开始的杀敌数和ADD指令时，进行更新操作，在进行qyery时，进行查询操作，线段树主要维护某个区间内的士兵的杀敌总数，详见代码：

C++ Code

<table style="width:100%; font-family:'Consolas','Courier New'; font-size:12px; vertical-align:text-top; line-height:15px"> 
 <tbody> 
 <tr> 
 <td style="color:#008284; background-color:#e3e3e3; vertical-align:text-top"> 
 <div style="margin:7px; text-align:right; white-space:nowrap">
 1 
 2 
 3 
 4 
 5 
 6 
 7 
 8 
 9 
 10 
 11 
 12 
 13 
 14 
 15 
 16 
 17 
 18 
 19 
 20 
 21 
 22 
 23 
 24 
 25 
 26 
 27 
 28 
 29 
 30 
 31 
 32 
 33 
 34 
 35 
 36 
 37 
 38 
 39 
 40 
 41 
 42 
 43 
 44 
 45 
 46 
 47 
 48 
 49 
 50 
 51 
 52 
 53 
 54 
 55 
 56 
 57 
 58 
 59 
 60 
 61 
 62 
 63 
 64 
 65 
 66 
 67 
 68 
 69 
 70 
 71 
 72 
 73 
 74 
 75 
 76 
 77 
 78 
 79 
 80 
 81 
 82 
 83 
 84 
 85 
 86 
 87 
 88 
 89 
 90 
 91 
 
 </div> </td> 
 <td style="background-color:#008284; padding:1px"> 
 <div style="border:1px #008284 solid"></div> </td> 
 <td style="background-color:rgb(239,239,239); width:100%; vertical-align:text-top"> 
 <div style="margin:7px"> 
 #include&lt;bits/stdc++.h&gt; 
 
 #define&nbsp;maxn&nbsp; 
 1000000 
 
 using&nbsp; 
 namespace&nbsp;std; 
 
 int&nbsp;b1[maxn],&nbsp;sum; 
 
 struct&nbsp;Node 
 { 
 &nbsp;&nbsp;&nbsp;&nbsp; 
 int&nbsp;left; 
 ///左边界 &nbsp;&nbsp;&nbsp;&nbsp; 
 int&nbsp;right; 
 ///右边界 &nbsp;&nbsp;&nbsp;&nbsp; 
 int&nbsp;num; 
 ///杀敌人数 }&nbsp;node[maxn&nbsp;*&nbsp; 
 4]; 
 
 
 void&nbsp;buid( 
 int&nbsp;i,&nbsp; 
 int&nbsp;left,&nbsp; 
 int&nbsp;right) 
 { 
 &nbsp;&nbsp;&nbsp;&nbsp; 
 ///建树 &nbsp;&nbsp;&nbsp;&nbsp;node[i].left&nbsp;=&nbsp;left; 
 &nbsp;&nbsp;&nbsp;&nbsp;node[i].right&nbsp;=&nbsp;right; 
 &nbsp;&nbsp;&nbsp;&nbsp;node[i].num&nbsp;=&nbsp; 
 0;&nbsp; 
 ///杀敌人数，初始化为零 &nbsp;&nbsp;&nbsp;&nbsp; 
 if(left&nbsp;==&nbsp;right) 
 &nbsp;&nbsp;&nbsp;&nbsp;{ 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;b1[left]&nbsp;=&nbsp;i;&nbsp; 
 ///存储第left号士兵，在线段树内的节点编号 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 return&nbsp;; 
 &nbsp;&nbsp;&nbsp;&nbsp;} 
 &nbsp;&nbsp;&nbsp;&nbsp; 
 int&nbsp;mid&nbsp;=&nbsp;(left&nbsp;+&nbsp;right)&nbsp;/&nbsp; 
 2; 
 &nbsp;&nbsp;&nbsp;&nbsp;buid(i&nbsp;&lt;&lt;&nbsp; 
 1,&nbsp;left,&nbsp;mid); 
 &nbsp;&nbsp;&nbsp;&nbsp;buid(i&nbsp;&lt;&lt;&nbsp; 
 1&nbsp;|&nbsp; 
 1,&nbsp;mid&nbsp;+&nbsp; 
 1,&nbsp;right); 
 } 
 
 
 void&nbsp;update( 
 int&nbsp;i,&nbsp; 
 int&nbsp;add) 
 { 
 &nbsp;&nbsp;&nbsp;&nbsp; 
 ///更新操作 &nbsp;&nbsp;&nbsp;&nbsp; 
 if(i&nbsp;==&nbsp; 
 1) 
 &nbsp;&nbsp;&nbsp;&nbsp;{ 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;node[i].num&nbsp;+=&nbsp;add; 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 return&nbsp;; 
 &nbsp;&nbsp;&nbsp;&nbsp;} 
 &nbsp;&nbsp;&nbsp;&nbsp;node[i].num&nbsp;+=&nbsp;add; 
 &nbsp;&nbsp;&nbsp;&nbsp;update(i&nbsp;&gt;&gt;&nbsp; 
 1,&nbsp;add); 
 } 
 
 
 void&nbsp;query( 
 int&nbsp;i,&nbsp; 
 int&nbsp;l,&nbsp; 
 int&nbsp;r) 
 { 
 &nbsp;&nbsp;&nbsp;&nbsp; 
 ///查询操作 &nbsp;&nbsp;&nbsp;&nbsp; 
 if(node[i].left&nbsp;==&nbsp;l&nbsp;&amp;&amp;&nbsp;node[i].right&nbsp;==&nbsp;r) 
 &nbsp;&nbsp;&nbsp;&nbsp;{ 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;sum&nbsp;+=&nbsp;node[i].num; 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 return&nbsp;; 
 &nbsp;&nbsp;&nbsp;&nbsp;} 
 &nbsp;&nbsp;&nbsp;&nbsp;i&nbsp;=&nbsp;i&nbsp;&lt;&lt;&nbsp; 
 1; 
 &nbsp;&nbsp;&nbsp;&nbsp; 
 if(l&nbsp;&lt;=&nbsp;node[i].right) 
 &nbsp;&nbsp;&nbsp;&nbsp;{ 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 if(r&nbsp;&lt;=&nbsp;node[i].right) 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;query(i,&nbsp;l,&nbsp;r); 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 else 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;query(i,&nbsp;l,&nbsp;node[i].right); 
 &nbsp;&nbsp;&nbsp;&nbsp;} 
 &nbsp;&nbsp;&nbsp;&nbsp;i++; 
 &nbsp;&nbsp;&nbsp;&nbsp; 
 if(r&nbsp;&gt;=&nbsp;node[i].left) 
 &nbsp;&nbsp;&nbsp;&nbsp;{ 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 if(l&nbsp;&gt;=&nbsp;node[i].left) 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;query(i,&nbsp;l,&nbsp;r); 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 else 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;query(i,&nbsp;node[i].left,&nbsp;r); 
 &nbsp;&nbsp;&nbsp;&nbsp;} 
 } 
 
 
 int&nbsp;main() 
 { 
 &nbsp;&nbsp;&nbsp;&nbsp; 
 int&nbsp;n,&nbsp;m,&nbsp;a,&nbsp;b,&nbsp;c; 
 &nbsp;&nbsp;&nbsp;&nbsp; 
 char&nbsp;s[ 
 10]; 
 &nbsp;&nbsp;&nbsp;&nbsp;scanf( 
 "%d&nbsp;%d",&nbsp;&amp;n,&nbsp;&amp;m); 
 &nbsp;&nbsp;&nbsp;&nbsp;buid( 
 1,&nbsp; 
 1,&nbsp;n); 
 &nbsp;&nbsp;&nbsp;&nbsp; 
 for( 
 int&nbsp;i&nbsp;=&nbsp; 
 1;&nbsp;i&nbsp;&lt;=&nbsp;n;&nbsp;i++) 
 &nbsp;&nbsp;&nbsp;&nbsp;{ 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;scanf( 
 "%d",&nbsp;&amp;c); 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;update(b1[i],&nbsp;c); 
 &nbsp;&nbsp;&nbsp;&nbsp;} 
 &nbsp;&nbsp;&nbsp;&nbsp; 
 while(m--) 
 &nbsp;&nbsp;&nbsp;&nbsp;{ 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;scanf( 
 "%s&nbsp;%d&nbsp;%d",&nbsp;s,&nbsp;&amp;a,&nbsp;&amp;b); 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 if(strcmp(s,&nbsp; 
 "QUERY")&nbsp;==&nbsp; 
 0) 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;{ 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;sum&nbsp;=&nbsp; 
 0; 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;query( 
 1,&nbsp;a,&nbsp;b); 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;printf( 
 "%d\n",&nbsp;sum); 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;} 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 else 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;update(b1[a],&nbsp;b); 
 &nbsp;&nbsp;&nbsp;&nbsp;} 
 &nbsp;&nbsp;&nbsp;&nbsp; 
 return&nbsp; 
 0; 
 } 
 
 </div> </td> 
 </tr> 
 </tbody> 
</table>