?

士兵殺敵（四）

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

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

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

輸入

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

輸出

對(duì)于每次查詢輸出此人的軍功，每個(gè)查詢的輸出占一行。

樣例輸入

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

樣例輸出

10 60 1 /* 功能Function Description: NYOJ-123 士兵殺敵四------樹樁數(shù)組--插線問(wèn)點(diǎn) 2 開發(fā)環(huán)境Environment: DEV C++ 4.9.9.1 3 技術(shù)特點(diǎn)Technique: 4 版本Version: 5 作者Author: 可笑癡狂 6 日期Date: 20120807 7 備注Notes: 8 */ 9 10 // 代碼一：----樹狀數(shù)組（插線問(wèn)點(diǎn)） 11 #include<stdio.h> 12 #include<string.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(i<=M) 24 { 25 a[i]+=num; 26 i+=lowbit(i); 27 } 28 } 29 30 int getsum(int i) 31 { 32 int sum=0; 33 while(i>0) 34 { 35 sum+=a[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(i=0;i<T;++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(end+1,-k); 54 } 55 else 56 { 57 scanf("%d",&k); 58 printf("%d\n",getsum(k)); //輸出第k個(gè)人的軍工 59 } 60 } 61 return 0; 62 }

?

?

1 //代碼二： 2 //-----線段樹(超時(shí)了----應(yīng)該是代碼寫的大材小用了，本題只用查詢一個(gè)點(diǎn)， 3 //自己寫的插入函數(shù)可以把線段都更新了，適用于查詢?nèi)我鈪^(qū)間的軍工總和，把查詢函數(shù)稍加改進(jìn)就能查線段了) 4 #include<stdio.h> 5 #include<malloc.h> 6 7 struct node 8 { 9 int lc,rc; 10 int sum; 11 }*tree; 12 13 void build(int s,int t,int T) 14 { 15 int mid=(s+t)>>1; 16 tree[T].lc=s; 17 tree[T].rc=t; 18 tree[T].sum=0; 19 if(s==t) 20 return ; 21 build(s,mid,T<<1); 22 build(mid+1,t,(T<<1)|1); 23 } 24 25 void insert(int s,int t,int add,int T) 26 { 27 if(tree[T].lc>t||tree[T].rc<s) 28 return ; 29 else if(s<tree[T].lc&&t<=tree[T].rc) 30 tree[T].sum+=add*(t-tree[T].lc+1); 31 else if(s>=tree[T].lc&&t<=tree[T].rc) 32 tree[T].sum+=add*(t-s+1); 33 else if(s>=tree[T].lc&&t>tree[T].rc) 34 tree[T].sum+=add*(tree[T].rc-s+1); 35 else 36 tree[T].sum+=add*(tree[T].rc-tree[T].lc+1); 37 if(tree[T].lc==tree[T].rc) 38 return ; 39 insert(s,t,add,T<<1); 40 insert(s,t,add,(T<<1)|1); 41 } 42 43 int qurry(int k,int T) 44 { 45 int mid=(tree[T].lc+tree[T].rc)>>1; 46 if(k<tree[T].lc||k>tree[T].rc) //不在此范圍內(nèi)直接跳出 47 return 0; 48 if(tree[T].lc==tree[T].rc) 49 return tree[T].sum; 50 if(k<=mid) 51 return qurry(k,T<<1); 52 else 53 return qurry(k,(T<<1)|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(i=0;i<T;++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個(gè)人的軍工 75 } 76 } 77 return 0; 78 }

?

總結(jié)

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

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