當(dāng)前位置:首頁 > 芯聞號(hào) > 充電吧
[導(dǎo)讀]題面:敵兵布陣 Time Limit: 2000/1000 MS (Java/Others)????Memory Limit: 65536/32768 K (Java/Others)Total Sub


題面:

敵兵布陣 Time Limit: 2000/1000 MS (Java/Others)????Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 61888????Accepted Submission(s): 26149


Problem Description C國的死對(duì)頭A國這段時(shí)間正在進(jìn)行軍事演習(xí),所以C國間諜頭子Derek和他手下Tidy又開始忙乎了。A國在海岸線沿直線布置了N個(gè)工兵營地,Derek和Tidy的任務(wù)就是要監(jiān)視這些工兵營地的活動(dòng)情況。由于采取了某種先進(jìn)的監(jiān)測(cè)手段,所以每個(gè)工兵營地的人數(shù)C國都掌握的一清二楚,每個(gè)工兵營地的人數(shù)都有可能發(fā)生變動(dòng),可能增加或減少若干人手,但這些都逃不過C國的監(jiān)視。
中央情報(bào)局要研究敵人究竟演習(xí)什么戰(zhàn)術(shù),所以Tidy要隨時(shí)向Derek匯報(bào)某一段連續(xù)的工兵營地一共有多少人,例如Derek問:“Tidy,馬上匯報(bào)第3個(gè)營地到第10個(gè)營地共有多少人!”Tidy就要馬上開始計(jì)算這一段的總?cè)藬?shù)并匯報(bào)。但敵兵營地的人數(shù)經(jīng)常變動(dòng),而Derek每次詢問的段都不一樣,所以Tidy不得不每次都一個(gè)一個(gè)營地的去數(shù),很快就精疲力盡了,Derek對(duì)Tidy的計(jì)算速度越來越不滿:"你個(gè)死肥仔,算得這么慢,我炒你魷魚!”Tidy想:“你自己來算算看,這可真是一項(xiàng)累人的工作!我恨不得你炒我魷魚呢!”無奈之下,Tidy只好打電話向計(jì)算機(jī)專家Windbreaker求救,Windbreaker說:“死肥仔,叫你平時(shí)做多點(diǎn)acm題和看多點(diǎn)算法書,現(xiàn)在嘗到苦果了吧!”Tidy說:"我知錯(cuò)了。。。"但Windbreaker已經(jīng)掛掉電話了。Tidy很苦惱,這么算他真的會(huì)崩潰的,聰明的讀者,你能寫個(gè)程序幫他完成這項(xiàng)工作嗎?不過如果你的程序效率不夠高的話,Tidy還是會(huì)受到Derek的責(zé)罵的.
?
Input 第一行一個(gè)整數(shù)T,表示有T組數(shù)據(jù)。
每組數(shù)據(jù)第一行一個(gè)正整數(shù)N(N<=50000),表示敵人有N個(gè)工兵營地,接下來有N個(gè)正整數(shù),第i個(gè)正整數(shù)ai代表第i個(gè)工兵營地里開始時(shí)有ai個(gè)人(1<=ai<=50)。
接下來每行有一條命令,命令有4種形式:
(1) Add i j,i和j為正整數(shù),表示第i個(gè)營地增加j個(gè)人(j不超過30)
(2)Sub i j ,i和j為正整數(shù),表示第i個(gè)營地減少j個(gè)人(j不超過30);
(3)Query i j ,i和j為正整數(shù),i<=j,表示詢問第i到第j個(gè)營地的總?cè)藬?shù);
(4)End 表示結(jié)束,這條命令在每組數(shù)據(jù)最后出現(xiàn);
每組數(shù)據(jù)最多有40000條命令
?
Output 對(duì)第i組數(shù)據(jù),首先輸出“Case i:”和回車,
對(duì)于每個(gè)Query詢問,輸出一個(gè)整數(shù)并回車,表示詢問的段中的總?cè)藬?shù),這個(gè)數(shù)保持在int以內(nèi)。
?
Sample Input


1 10 1 2 3 4 5 6 7 8 9 10 Query 1 3 Add 3 6 Query 2 7 Sub 10 2 Add 6 3 Query 3 10 End ?
Sample Output


Case 1: 6 33 59


題目大意:

? ? 一共有n個(gè)兵營,每個(gè)兵營初始有ai個(gè)人。對(duì)應(yīng)3種操作。

操作一:

? ? Q A B 詢問A到B共多少人。

操作二:

? ? A X Y 給X兵營加Y個(gè)人。

操作三:

? ? S X Y 給X兵營減去Y個(gè)人。


解題:

? ? 直接做,復(fù)雜度過高。用線段樹維護(hù),區(qū)間和。每種操作復(fù)雜度都為log(n)。


代碼:


#include#include#define?maxn?50010
#define?ls?i<<1
#define?rs?(i<<1)|1
using?namespace?std;
struct?node
{
	//左右邊界,區(qū)間和?
????int?l,r,sum;
}stree[maxn<>1;
????build(ls,l,mid);
????build(rs,mid+1,r);
????//維護(hù)區(qū)間和?
????push_up(i);
}
//單點(diǎn)更新?
void?update(int?i,int?x,int?v)
{
????if(x==stree[i].l&&x==stree[i].r)
????{
????????stree[i].sum+=v;
????????return;
????}
????//根據(jù)相對(duì)位置,向下遞歸?
????int?mid=(stree[i].l+stree[i].r)>>1;
????if(x>1;
????if(rmid)
????????return?query(rs,l,r);
????else
????????return?query(ls,l,mid)+query(rs,mid+1,r);
}?
int?main()
{
????int?t,n,tmp,x,v;
????char?oper[10];
????scanf("%d",&t);
????for(int?i=1;i<=t;i++)
????{
??????printf("Case?%d:n",i);
??????scanf("%d",&n);
??????//建樹?
??????build(1,1,n);
??????//初值?
??????for(int?j=1;j<=n;j++)
??????{
??????????scanf("%d",&tmp);
??????????update(1,j,tmp);
??????}
??????while(1)
??????{
??????????scanf("%s",oper);
??????????if(oper[0]=='E')
??????????????break;
??????????else?if(oper[0]=='A')
??????????{
?????????????scanf("%d%d",&x,&v);
?????????????update(1,x,v);
??????????}
??????????else?if(oper[0]=='S')
??????????{
??????????????scanf("%d%d",&x,&v);
??????????????update(1,x,-v);
??????????}
??????????else
??????????{
??????????????scanf("%d%d",&x,&v);
??????????????printf("%dn",query(1,x,v));
??????????}
??????}
????}
????return?0;
}



本站聲明: 本文章由作者或相關(guān)機(jī)構(gòu)授權(quán)發(fā)布,目的在于傳遞更多信息,并不代表本站贊同其觀點(diǎn),本站亦不保證或承諾內(nèi)容真實(shí)性等。需要轉(zhuǎn)載請(qǐng)聯(lián)系該專欄作者,如若文章內(nèi)容侵犯您的權(quán)益,請(qǐng)及時(shí)聯(lián)系本站刪除。
換一批
延伸閱讀

9月2日消息,不造車的華為或?qū)⒋呱龈蟮莫?dú)角獸公司,隨著阿維塔和賽力斯的入局,華為引望愈發(fā)顯得引人矚目。

關(guān)鍵字: 阿維塔 塞力斯 華為

倫敦2024年8月29日 /美通社/ -- 英國汽車技術(shù)公司SODA.Auto推出其旗艦產(chǎn)品SODA V,這是全球首款涵蓋汽車工程師從創(chuàng)意到認(rèn)證的所有需求的工具,可用于創(chuàng)建軟件定義汽車。 SODA V工具的開發(fā)耗時(shí)1.5...

關(guān)鍵字: 汽車 人工智能 智能驅(qū)動(dòng) BSP

北京2024年8月28日 /美通社/ -- 越來越多用戶希望企業(yè)業(yè)務(wù)能7×24不間斷運(yùn)行,同時(shí)企業(yè)卻面臨越來越多業(yè)務(wù)中斷的風(fēng)險(xiǎn),如企業(yè)系統(tǒng)復(fù)雜性的增加,頻繁的功能更新和發(fā)布等。如何確保業(yè)務(wù)連續(xù)性,提升韌性,成...

關(guān)鍵字: 亞馬遜 解密 控制平面 BSP

8月30日消息,據(jù)媒體報(bào)道,騰訊和網(wǎng)易近期正在縮減他們對(duì)日本游戲市場(chǎng)的投資。

關(guān)鍵字: 騰訊 編碼器 CPU

8月28日消息,今天上午,2024中國國際大數(shù)據(jù)產(chǎn)業(yè)博覽會(huì)開幕式在貴陽舉行,華為董事、質(zhì)量流程IT總裁陶景文發(fā)表了演講。

關(guān)鍵字: 華為 12nm EDA 半導(dǎo)體

8月28日消息,在2024中國國際大數(shù)據(jù)產(chǎn)業(yè)博覽會(huì)上,華為常務(wù)董事、華為云CEO張平安發(fā)表演講稱,數(shù)字世界的話語權(quán)最終是由生態(tài)的繁榮決定的。

關(guān)鍵字: 華為 12nm 手機(jī) 衛(wèi)星通信

要點(diǎn): 有效應(yīng)對(duì)環(huán)境變化,經(jīng)營業(yè)績穩(wěn)中有升 落實(shí)提質(zhì)增效舉措,毛利潤率延續(xù)升勢(shì) 戰(zhàn)略布局成效顯著,戰(zhàn)新業(yè)務(wù)引領(lǐng)增長 以科技創(chuàng)新為引領(lǐng),提升企業(yè)核心競(jìng)爭(zhēng)力 堅(jiān)持高質(zhì)量發(fā)展策略,塑強(qiáng)核心競(jìng)爭(zhēng)優(yōu)勢(shì)...

關(guān)鍵字: 通信 BSP 電信運(yùn)營商 數(shù)字經(jīng)濟(jì)

北京2024年8月27日 /美通社/ -- 8月21日,由中央廣播電視總臺(tái)與中國電影電視技術(shù)學(xué)會(huì)聯(lián)合牽頭組建的NVI技術(shù)創(chuàng)新聯(lián)盟在BIRTV2024超高清全產(chǎn)業(yè)鏈發(fā)展研討會(huì)上宣布正式成立。 活動(dòng)現(xiàn)場(chǎng) NVI技術(shù)創(chuàng)新聯(lián)...

關(guān)鍵字: VI 傳輸協(xié)議 音頻 BSP

北京2024年8月27日 /美通社/ -- 在8月23日舉辦的2024年長三角生態(tài)綠色一體化發(fā)展示范區(qū)聯(lián)合招商會(huì)上,軟通動(dòng)力信息技術(shù)(集團(tuán))股份有限公司(以下簡(jiǎn)稱"軟通動(dòng)力")與長三角投資(上海)有限...

關(guān)鍵字: BSP 信息技術(shù)
關(guān)閉
關(guān)閉