acm-icpc培訓(xùn)匯編3數(shù)據(jù)結(jié)構(gòu)、動(dòng)態(tài)分冊(cè)號(hào)

序2012年5月，哈爾濱理工大學(xué)承辦了ACM-ICPC黑龍江省第七屆大學(xué)生程序設(shè)計(jì)競(jìng)201110月確定學(xué)校承辦本屆競(jìng)賽后，我就給齊同學(xué)半年多的工作還是很有成效，不僅帶著、姜喜鵬、程憲慶、盧俊達(dá)等隊(duì)員開(kāi)發(fā)OJOJ，還集體帶出了幾個(gè)比較像樣的新隊(duì)員，使得今年省賽我校取得了很好的成績(jī)（當(dāng)然，也承蒙哈工大和哈工程關(guān)照，沒(méi)有派出全部大牛來(lái)參在2011年9月之前，我對(duì)ACM-ICPC關(guān)心甚少。但是，我注意到我校隊(duì)員學(xué)習(xí)、訓(xùn)練沒(méi)有統(tǒng)一的資料，也沒(méi)有按照競(jìng)賽所需知識(shí)體系全面系統(tǒng)培訓(xùn)新隊(duì)員。2011-2012年度的學(xué)生們做了一個(gè)較詳細(xì)的培訓(xùn)計(jì)劃，每周都會(huì)給2011級(jí)新隊(duì)員上課，也會(huì)對(duì)老隊(duì)員進(jìn)的，新生也是雜七雜八看些資料和做題。在培訓(xùn)的規(guī)范性上欠缺很多，當(dāng)然這個(gè)責(zé)任不在學(xué)生。2011年9月，我曾給老隊(duì)員提出編寫(xiě)培訓(xùn)資料這個(gè)任務(wù)，一是老隊(duì)員人數(shù)少，有的還要去等企業(yè)實(shí)習(xí)；二是老隊(duì)員要開(kāi)發(fā)、改造OJ；三是培訓(xùn)新隊(duì)員也很耗費(fèi)精力，2012年8月底，2012級(jí)新生滿懷夢(mèng)想和憧憬來(lái)到學(xué)校，部分同學(xué)也被ACM-ICPC深深吸引。面對(duì)這個(gè)新群體的培訓(xùn)，如何提高效率和質(zhì)量這個(gè)老問(wèn)題又浮現(xiàn)出來(lái)。市面現(xiàn)在已經(jīng)有了各種各樣的ACM-ICPC培訓(xùn)，主要算法和解題思路都有了廣泛深入的分析和討論。同時(shí)，互聯(lián)網(wǎng)博客、BBS等中也隱藏著諸多大牛對(duì)某些算法的論述和參賽感悟。，做一個(gè)資料匯編，采擷各家之精要，對(duì)應(yīng)該會(huì)有較大幫助，至少一可以減少感謝ACM-ICPC先輩們作出的杰出工作和貢獻(xiàn)，使得我們這些后繼者們可以站在巨人新201210本資料為哈爾濱理工大學(xué)ACM-ICPC集訓(xùn)隊(duì)自編自用的，商業(yè)銷(xiāo)售目本分冊(cè)大綱由編寫(xiě)，內(nèi)容由、、盧俊達(dá)、等分別編寫(xiě)和校核。本分冊(cè)內(nèi)容大部分采編自各OJ、互聯(lián)網(wǎng)和部分書(shū)籍。在此，對(duì)所有文獻(xiàn)和試題的 哈爾濱理工大學(xué)評(píng)測(cè)系統(tǒng)（Hrbust-OJ）：http://a 201212 編寫(xiě)說(shuō) 第1章數(shù)據(jù)結(jié) 散 散列表的概 散列函數(shù)的構(gòu)造方 處理的方 散列表上的運(yùn) 散列表的應(yīng) 附：字符串哈希函 并查 并查集基本原 并查集的時(shí)間復(fù)雜度分析和優(yōu) 并查集樣例代 ..................................................................................................................二叉 二叉堆的概 二叉堆的基本操 堆排 經(jīng)典題 樹(shù)狀數(shù) 基本原 樹(shù)狀數(shù)組例 其他推薦例 線段 線段樹(shù)的介 線段樹(shù)模板代 經(jīng)典題 隨機(jī)平衡二叉查找 概 總 經(jīng)典題 其他例 伸展樹(shù)(Splay 概 基本操 在伸展樹(shù)中對(duì)區(qū)間進(jìn)行操 實(shí)例分析—NOI2005數(shù)列 和線段樹(shù)的比 伸展樹(shù)例 第2章動(dòng)態(tài)規(guī) 遞 遞推原 一般的思 經(jīng)典題 背包問(wèn) 背包的入門(mén)和進(jìn) 經(jīng)典題 區(qū)間動(dòng)態(tài)規(guī) 2.3.1..........................................................................................................................NOIp2000乘積最 POJ1141Brackets NOIp2006能量項(xiàng) NOI2001棋盤(pán)分 其他題 狀態(tài)壓縮動(dòng)態(tài)規(guī) 狀態(tài)壓縮的原 一般的解題思 經(jīng)典題 擴(kuò)展變 樹(shù)形動(dòng)態(tài)規(guī) 樹(shù)形動(dòng)態(tài)規(guī)劃介 解題思 經(jīng)典題 利用單調(diào)性質(zhì)優(yōu)化動(dòng)態(tài)規(guī) 利用單調(diào)性優(yōu)化最長(zhǎng)上升子序 單調(diào)隊(duì) 直接利用單調(diào)隊(duì)列解 單調(diào)隊(duì)列優(yōu)化動(dòng)態(tài)規(guī) 利用斜率的單調(diào) 擴(kuò)展推 第1散列表 編寫(xiě)：校核：散列B-樹(shù)上的查找。它不以關(guān)鍵字的字，查找的期望時(shí)間為O(1)。設(shè)所有可能出現(xiàn)的關(guān)鍵字集合記為U(簡(jiǎn)稱(chēng)全集)。實(shí)際發(fā)生(即實(shí)際)的關(guān)鍵字集合記為K（|K|比|U|小得多。（m=O(|U|)鍵字為自變量，以h為函數(shù)的運(yùn)算結(jié)果就是相應(yīng)結(jié)點(diǎn)的地址。從而達(dá)到在O(1)時(shí)間內(nèi)h：U→{0，1，2，…，m-1}h為散列函數(shù)(HashFunction)T為散列表(HashTable)④將結(jié)點(diǎn)按其關(guān)鍵字的散列地 到散列表中的過(guò)程稱(chēng)為散列（1）(Collision)或碰撞。發(fā)生的兩個(gè)關(guān)鍵字稱(chēng)為該散列函數(shù)的同義詞(Synonym)【例】上圖中的k2≠k5，但h(k2)=h(k5)，故k2和K5所在的結(jié)點(diǎn)的地址相同（2）安全避免的條①其一是能完全避免。通常情況下，h是一個(gè)壓縮映像。雖然|K|≤m，但|U|>mh，也不可能完全避免。因此，只能在設(shè)計(jì)h時(shí)盡可能使最少。同時(shí)還需要確定解決的方法，使發(fā)生的同義詞能夠到表中。（4）影響的因mn分別表示表長(zhǎng)和表中填人的結(jié)點(diǎn)數(shù)，則將α=n/m散列函數(shù)的構(gòu)何一個(gè)位置上。也就是說(shuō)，散列函數(shù)能將子集K隨機(jī)均勻地分布在表的地址集{0，1，…，m-1}上，以使最小化。 intHash(intkey){key4key*=keykey/=100//先求平方值，后去掉末尾的兩位數(shù)returnkey％1000；//取中間三位數(shù)作為散列地址返回該方法是最為簡(jiǎn)單常用的法。它是以表長(zhǎng)m來(lái)除關(guān)鍵字，取其余數(shù)作為散列地址，即h(key)=key％m地址，而與無(wú)關(guān)。于是不同而低位相同的關(guān)鍵字均互為同義詞。10m=100時(shí)，159，259，359，…，等小數(shù)部分；然后用m乘以該小數(shù)后取整。即：次冪。雖然該方法對(duì)任何A的值都適用，但對(duì)某些值效果會(huì)更好。Knuth建議選取intHash(intdoubled=key*A//Am (int)(m*(d-(int)d))；//(int)表示強(qiáng)制轉(zhuǎn)換后面的表達(dá)式為}處理的方通常有兩類(lèi)方法處理：開(kāi)放定址(OpenAddressing)法和拉鏈(Chaining)法。前者T[0..m-1]中；后者通常是將互為同義詞的結(jié)點(diǎn)鏈成一個(gè)單鏈表，而將此鏈表的頭指針?lè)旁谏⒘斜鞹[0..m-1]中。用開(kāi)放定址法解決的做法是：當(dāng)發(fā)生時(shí)，使用某種探查(亦稱(chēng)探測(cè))技術(shù)在散列表中形成一個(gè)探查(測(cè))序列。沿此序列逐個(gè)單元地查找，直到找到給定的關(guān)鍵字，或者碰到一個(gè)開(kāi)放的地址(即該地址單元為空)為止（若要插入，在探查到開(kāi)放的地址，則可將待插入的新結(jié)點(diǎn)存人該地址單元。查找時(shí)探查到開(kāi)放的地址則表明表中無(wú)待查的關(guān)鍵字，即查找失敗。【例】關(guān)鍵字均為非負(fù)數(shù)時(shí)，可用"-"來(lái)表示空單元，而關(guān)鍵字為字符串時(shí)，空單元應(yīng)是空串。hi=(h(key)+di)％m1≤i≤m-①h(key)為散列函數(shù)，di為增量序列，m②h(key)是初始的探查位置，后續(xù)的探查位置依次是hlh2hm-1，即h(key)，hl，h2，…，hm- hi=(h(key)+di)％m0≤i≤m-1開(kāi)放定址法要求散列表的裝填因子α≤l，實(shí)用中取α0.50.9①線性探查法(LinearT[0..m-1]d(h(key)=d)，則最即:dT[d]T[d+1]T[m-1]，此后又循環(huán)到T[0]，T[1]，…，直到探查到T[d-1]為止。若當(dāng)前探查的單元為空，則表示查找失?。ㄈ羰遣迦雱t將key寫(xiě)入其中 T[d-1]key，則無(wú)論是查找還是插入均意味著hi=(h(key)+i)％m0≤i≤m-1//即9.1】已知一組關(guān)鍵字為(26，36，41，38，44，15，68，12，06，51)，用除余法構(gòu)造散列函數(shù)，用線性探查法解決構(gòu)造這組關(guān)鍵字的散列表。解答:為了減少，通常令裝填因子α<l。這里關(guān)鍵字個(gè)數(shù)n=10，不妨取m=13，此時(shí)α≈0.77，散列表為T(mén)[0..12]，散列函數(shù)為：h(key)=key％13。由除余法的散列函數(shù)計(jì)算出的上述關(guān)鍵字序列的散列地址為3，12，6，12)T[2]，T[12]T[5]中。768315T[4]8121238hl=(12+1)％13=0T[0]26h2=(12+2)％13=112插入其中。906T[6]51插人時(shí)，因探查的12，0，1，…，651T[7]中。 /course_ware/data_structure/web/flashhtml/kaifang.htm用線性探查法解決時(shí)，當(dāng)表中i,i+1，…，i+k的位置上已有結(jié)點(diǎn)時(shí)，一個(gè)散列地同一個(gè)后繼散列地址的現(xiàn)象稱(chēng)為或堆積(Clustering)。這將造成不是同義詞的結(jié)點(diǎn)也處【例】上例中，h(15)=2，h(68)=3156815和同義詞41的時(shí)，15搶先占用了T[3]，這就使得插入68時(shí)，這兩個(gè)本來(lái)不應(yīng)該發(fā)生③雙重散列法hi=(h(key)+i*h1(key))％m0≤i≤m-1//即該方法使用了兩個(gè)散列函數(shù)h(key)和h1(key)，故也稱(chēng)為雙散列函數(shù)探查法。定義h1(key)的方法較多，但無(wú)論采用什么方法定義，都必須使h1(key)的值和m互素，才能使發(fā)生的同義詞地址均勻地分布在整個(gè)表中，否則可能造成同義詞地址的循mh1(key)1m-1m互素，因此，我拉鏈法解決的做法是：將所有關(guān)鍵字為同義詞的結(jié)點(diǎn)在同一個(gè)單鏈表中。若mmT[0..m-1]iT[i]為頭指針的單鏈表中。T中各分量的初值均應(yīng)為空指針。在拉鏈法中，裝填因子α可以大于1，但一般均取α≤1。9.113h(key)=key％13，散列表T[0..12]。h(key)=ii個(gè)單鏈表時(shí)，既可插入在鏈表的頭上，也可以keyi個(gè)鏈表時(shí)，才能將它插入表中，所以也 /course_ware/data_structure/web/flashhtml/llf.htm開(kāi)放定址法為減少，要求裝填因子α較小，故當(dāng)結(jié)點(diǎn)規(guī)模較大時(shí)會(huì)浪費(fèi)很多空間。而拉鏈法中可取α≥1，且結(jié)點(diǎn)較大時(shí)，拉鏈法中增加的指針域可忽略不計(jì)，因在用拉鏈法構(gòu)造的散列表中，刪除結(jié)點(diǎn)的操作易于實(shí)現(xiàn)。只要簡(jiǎn)單地刪去鏈表法中，空地址單元(即開(kāi)放地址)都是查找失敗的條件。因此在用開(kāi)放地址法處理的散散列#defineNIL1空結(jié)點(diǎn)標(biāo)記依賴于關(guān)鍵字類(lèi)型，本節(jié)假定關(guān)鍵字均為非負(fù)整數(shù)#defineM997//表長(zhǎng)度依賴于應(yīng)用，但一般應(yīng)根據(jù)。確定m為一素?cái)?shù)typedefstruct{散列表結(jié)點(diǎn)類(lèi)型KeyTypekey；InfoType

散列表的查找過(guò)程和建表過(guò)程相似。假設(shè)給定的值為h(K)與給定值K比較。若相等則查找成功，否則按建表時(shí)設(shè)定的處理的方法找下一個(gè)地址。如此反復(fù)下去，直到某個(gè)地址單元為空(查找失敗)或者關(guān)鍵字比較相等(查找成功)為止。intHash(KeyTypek，int法

h是散列函數(shù)。Increment是求增量序列的函數(shù)，它依賴于解決的return(h(K)+Increment(i))％m；//Increment(i)} 函數(shù)中的h(K)Increment(i)可定義為return}returni;//}{//址inti=0//記錄探查次數(shù)*pos=Hash(K，i)；//求探查地址hiif(T[*pos].key==K)returnl；//查找成功返回if(T[*pos].key==NIL)return0；//查找到空結(jié)點(diǎn)返回}while(++i<m)//mreturn-1；//表滿且未找到時(shí)，查}Hashh(K)和增量函數(shù)法HashSearch中，相應(yīng)的算法【參見(jiàn)習(xí)題intpos，sign；sign=HashSearch(T，new.key，&pos)；//Tnewif(!sign)//找到一個(gè)開(kāi)放的地址poselse插人失敗printf("duplicatekey!")//重復(fù)的關(guān)鍵字else//sign<0 }intiError("Loadfactor>1")；T[i].key=NIL；//ifor(i=0;i<n；i++)依次將A[0..n-1]插入到散列表T[0..m-1]中}則不能將被刪結(jié)點(diǎn)的關(guān)鍵字置為NIL，而應(yīng)該將其置為特定的標(biāo)記DELETED。DELETED標(biāo)記時(shí)，將相應(yīng)的表單元視為一個(gè)空單元，將新結(jié)點(diǎn)插雖然散列表在關(guān)鍵字和位置之間建立了對(duì)應(yīng)關(guān)系，理想情況是無(wú)須關(guān)鍵字的比較就可找到待查關(guān)鍵字。但是由于的存在，散列表的查找過(guò)程仍是一個(gè)和關(guān)鍵字比較的9.19.2的散列表中，在結(jié)點(diǎn)的查找概率相等的假設(shè)下，線性探查法ASL=(1×6+2×2+3×l+9×1)/10=2.2線性探查法ASL=(1×7+2×2+3×1)/10=1.4//拉鏈法ASL=(10+1)/2=5.5////9.19.2的散列表中，在等概率情況下，查找不成功時(shí)的線性探查法和

n的函數(shù)，而是裝填因子α的函數(shù)。因此在設(shè)③αα越小，產(chǎn)生的機(jī)會(huì)就小，但α過(guò)小，空間的浪費(fèi)就過(guò)多。只要α選擇合適，散列表上的平均查找長(zhǎng)度就是一個(gè)常數(shù)，即散列表上查找的平均時(shí)間為O(1)。且每次比較后均能縮小下次的查找范圍，故查找速度更快，其平均時(shí)間為O(lgn)。而散列法是根據(jù)關(guān)鍵字直接求出地址的查找方法，其查找的期望時(shí)間為O(1)。散列用計(jì)算機(jī)隨機(jī)生成了N個(gè)0 （包含0 N211M2SampleInput20403267402089300400SampleOutput152032406789300分布的，問(wèn)題使用拉鏈法解決。當(dāng)然也可以直接使用C++STL的set容器，時(shí)間復(fù)雜度#include<stdio.h>#include<string.h>#include<iostream>#include<algorithm>usingnamespaceconstintMP=1007;structNode{intNode*Node*pnd[MP+1];Nodend[MP+1]; int int{intn,d,while(EOF!=scanf("%d",&n)){memset(pnd,0,t=t=for(inti=0;i<n;{scanf("%d",&d);p=d%MP;boolfound=false;Node*pt=pnd[p];while(pt){if(pt->d== true;break;}pt=pt-}if(!found) t].d= t].next=pnd[p]=&nd[ }}

= t,a[0]);for(inti=1;i< t;++i){printf("%d",}}return}POJ2002nn2個(gè)點(diǎn)，使得這四個(gè)點(diǎn)能夠成正先按他們的坐標(biāo)從小到大排序，xy，這一步只是從插入順序上優(yōu)化一下之后的哈希查找，哈希函數(shù)使用取余法，把x+y和除MOD取余。參考下圖，已知兩個(gè)點(diǎn)，然后做出兩個(gè)全等三角形。之后就得出結(jié)論(x1+|y1-y2|,y1+|x1-碼的枚舉方式使得需要將統(tǒng)計(jì)的結(jié)果除以2。#include<stdio.h>#include<string.h>#include<iostream>#include<algorithm>usingnamespaceconstintM=1031;structPoint{intx,Pointp[1024];intn;inthash[M+8],boolcmp(constPoint&a,constPoint&{if(a.x!=b.x)returna.x<b.x;returna.y}

inthashcode(constPoint{returnabs(tp.x+tp.y)%}boolhash_search(constPoint{intkey=hashcode(tp);inti=hash[key];while(i!=-1){if(tp.x==p[i].x&&tp.y==p[i].y)returntrue;i=}return}{intkey=hashcode(p[i]);next[i]=hash[key];hash[key]=}int{Pointp3,p4;intdx,dy,ans;while(1==scanf("%d",&n)&&n){for(inti=0;

i<n;i++){scanf("%d%d",&p[i].x,}sort(p,p+n,for(inti0inians=for(inti=0;i<n;for(intj=i+1;j<n;j++){intdx=p[j].x-p[i].x;intdy=p[j].y-p[i].y;p3.x=p[i].x+dy;p3.y=p[i].y-dx;if(hash_search(p3)){p4.x=p[j].x+p4.y=p[j].y-dx;if(hash_search(p4))}}}}return}POJ1840有以下等式：a1*x13+a2*x23+a3*x33+a4*x43+a5*x53=0。x1，x2，x3，x4，x5都就在情況下，x1,x2,x3,x4,x5共有多少種可能的取值？a1*x13+a2*x23(a3*x33+a4*x43+a5*x53)，先把所有a1*x13+a2*x23結(jié)果算出來(lái)，放進(jìn)哈希#include<stdio.h>#include<string.h>constintmaxn=constintprime Hash{intHash*hash[prime+1];intc[maxn];intx[maxn];intans;int{intt,Hash*for(inti=0;i<maxn;i++){scanf("%d",c+i);}memset(hash,0,for(x[0]=-50;x[0]<=50;x[0]++)iffor(x[1]=-50;x[1]<=50;x[1]++)if{t=-(x[0]*x[0]*x[0]*c[0]+x[1]*x[1]*x[1]*c[1]);p=(t>0?t:-t)%prime;ph=newHash;ph->v=t;ph->next=hash[p];hash[p]=ph;}ans=for(x[2]=-50;x[2]<=50;x[2]++)iffor(x[3]=-50;x[3]<=50;x[3]++)iffor(x[4]=-50;x[4]<=50;x[4]++)if{t=x[2]*x[2]*x[2]*c[2]+x[3]*x[3]*x[3]*c[3]+x[4]*x[4]*x[4]*c[4];p=(t>0?t:-t)%prime;ph=hash[p];while(ph){if(ph->v==ph=ph-}}return0;}POJ3349SnowflakeSnowSnowflakesPOJ2503BabelfishPOJ3274GoldBalanced附：字符串哈 //ELFHashunsignedintELFHash(char{unsignedinthash=0;unsignedintx=0;while(*str){hash=(hash<<4)+if((x=hash& L)!={hash^=(x>>24);hash&=~x;}}return(hash&}//BKDRHashunsignedintBKDRHash(char{unsignedintseed=131;//311311313 unsignedinthash=0;while{hash=hash*seed+}}

(hash& 編寫(xiě)：校核：并查N個(gè)元素的集合應(yīng)用問(wèn)題中，我們通常是在開(kāi)始時(shí)讓每個(gè)元素構(gòu)成一個(gè)單元間復(fù)雜度也極高，根本就不可能在比賽規(guī)定的運(yùn)行時(shí)間（1～3秒）內(nèi)計(jì)算出試題需要的結(jié)();查找這個(gè)節(jié)點(diǎn)所在集合：fin(v);我們用一個(gè)節(jié)點(diǎn)的標(biāo)號(hào)表示這個(gè)節(jié)點(diǎn)處在哪個(gè)集合v最上層的節(jié)點(diǎn)，也就是根。合并兩個(gè)不相交集合：join(x,y)yx判斷兩個(gè)元素是否屬于同一個(gè)集合：is_same(xy)，如果xy在同一集合內(nèi)，則返回5fa記錄每個(gè)節(jié)點(diǎn)的父節(jié)點(diǎn)，fa[i]i節(jié)點(diǎn)的父節(jié)點(diǎn)標(biāo)號(hào)，當(dāng)fa[i]=ii的父節(jié)點(diǎn)是他本身，那么i的所在的樹(shù)的根上就是i。=fa[1]= fa[2]=2;fa[3]=3;fa[4]=4;fa[5]=fa[1]= fa[2]=1;fa[3]=3;fa[4]=4;fa[5]=11212是在同一集合內(nèi)的。接下來(lái)我們合并1和3，讓fa[3]=1，即使得3的父節(jié)點(diǎn)為1，有：fa[1]=1; fa[2]=1;fa[3]=1;fa[4]=4;fa[5]=5;5353fa[5]=3。能得到下面的圖。我們根據(jù)fa[i]的值，能找4所在樹(shù)的根節(jié)點(diǎn)1，2的所在樹(shù)的根1，則可以判25是屬于同一棵樹(shù)內(nèi)的，同一個(gè)集合的。現(xiàn)在你應(yīng)該能寫(xiě)出每個(gè)節(jié)點(diǎn)的fa[i]值了。這里我們的節(jié)點(diǎn)標(biāo)號(hào)從0開(kāi)始。consintMAX_SIZE=100005;intfa[MAX_SIZE]; {intfor(i=0;i<MAX_SET_SIZE;++i)fa[i]=}intfind(int{if(fa[v]==v) returnv; //如果fa[vv，那么v就是樹(shù)的根節(jié)點(diǎn)了，返回vreturnfind(fa[v]);//上面一句沒(méi)成功，要找父節(jié)點(diǎn)的父節(jié)點(diǎn)}voidjoin(intx,int{intfxfind(x),fyfind(y);//xyif(fx!=fy){//如果他們的根節(jié)點(diǎn)不一樣，就是不在同一集合內(nèi)，可以合并fafx]fy;我們把y的的根節(jié)點(diǎn)的父節(jié)點(diǎn)設(shè)為x的最上層節(jié)點(diǎn)就行}}intis_same(intx,inty){}并查集的時(shí)間復(fù)雜度分析和優(yōu)find()操作，這個(gè)有些難確定，不過(guò)它的情況還是能確定的，如果對(duì)于每個(gè)節(jié)點(diǎn)，都有fa[i]=i–1，fa[0]=0，這棵樹(shù)在這種情況下就成有n個(gè)元素，那么總的查找次數(shù)，也就是find(v）調(diào)用次數(shù)為：123+…+n，有(n+1)*n/2，時(shí)間復(fù)雜O(n*n)，一般來(lái)講，init()只操作一次，find(v)和join(x,y)操作 O(q*n)如果q*n主要優(yōu)化find()函數(shù)。find()函數(shù)的目的是查找到一個(gè)節(jié)點(diǎn)的根節(jié)點(diǎn)，那么找到一個(gè)節(jié)xffa[x]=fx的父節(jié)點(diǎn)的時(shí)候，就能馬x節(jié)點(diǎn)的根節(jié)點(diǎn)。既然這樣，我們就直接將查找路徑上所有節(jié)點(diǎn)的父節(jié)點(diǎn)都設(shè)為f，這樣在查找這些節(jié)點(diǎn)的時(shí)候就能用兩次find()函數(shù)調(diào)用就找到了節(jié)點(diǎn)的根節(jié)點(diǎn)，大大加快intfind(int{if(fa[v]== returnreturnfa[v]=find(fa[v]);//路徑壓縮，直接賦值為找到的根節(jié)}ackerman函數(shù)的反函數(shù)——α（x。這里αAckerman函數(shù)的某個(gè)反函數(shù)，在很大的范圍內(nèi)（人類(lèi)目1080次方個(gè)原子，這小于前面所說(shuō)的范圍）這個(gè)函數(shù)的值 還有一個(gè)優(yōu)化，就是根據(jù)樹(shù)的深度來(lái)合并集合，具體怎么實(shí)現(xiàn)，請(qǐng)你自己上網(wǎng)查一下，相信你能完成它。并查constintMAX_SIZE=100005;intfather[MAX_SET_SIZE];void{intfor(i=0;i<MAX_SET_SIZE;++i)fa[i]=}intfind(int{if(fa[v]==v)returnreturn}

=find(faintis_same(intx,int{return(find(x)==}voidjoin(intx,int{intfx=find(x),fy=find(y);if(fx!=fy)fa[fx]=}Hrbustoj1073POJ2492ABug'sLifePOJ1182食物鏈Hrbustoj1073某種了某地區(qū)，該地區(qū)有N(1≤N≤50000)人，分別編號(hào)為0,1,...,N-1，現(xiàn)在0號(hào)已被確診，所有0的直接朋友和間接朋友都要被。例如：0與1是直接朋友，1與2≤10000)個(gè)直接朋友關(guān)系。如：0,20,2是直接朋友關(guān)系。請(qǐng)你編程計(jì)算，有多少人要被。N(1≤N≤50000),M(1≤M≤100000)，分別表示人UV(0UVN)表示一個(gè)直接朋友關(guān)系。輸出數(shù)據(jù)僅包含一個(gè)整數(shù)，為共需的人數(shù)（包含0號(hào)在內(nèi)。與0有過(guò)直接或者間接接觸的都是需要的人，簡(jiǎn)單的并查集應(yīng)用。#include<stdio.h>constintMAXN=50005;{}

find(intif(x!=f[x])f[x]=find(f[x]);returnf[x];voidunion_set(intx,int{intpx=find(x);intpy=if(px!=py)f[px]=}int{intcnt,f0,n,m,x,while(EOF!=scanf("%d%d",&n,&m))for(inti=0;i<MAXN;i++)f[i]=i;for(inti=0;i<m;i++){scanf("%d%d",&x,&y);union_set(x,y);}cnt=f0=for(inti=1;i<n;{if(f0==find(i))}}return}POJ2492ABug's題目大意：一個(gè)無(wú)聊的科學(xué)家說(shuō)只有兩個(gè)不同的昆蟲(chóng)能在一起，當(dāng)然是在沒(méi)有同性戀的情況下。給你幾對(duì)能在一起的昆蟲(chóng)，問(wèn)里面有沒(méi)有，也就是交配是否有沖突。輸入一個(gè)數(shù)t，表示測(cè)試組數(shù)。然后每組第一行兩個(gè)數(shù)字n,m，n表示有n只昆蟲(chóng)，1—n,mm行交配情況，每行兩個(gè)整數(shù)，表示這兩個(gè)編號(hào)的昆蟲(chóng)為異性，要進(jìn)行交配。要求統(tǒng)計(jì)交配過(guò)程中是否出現(xiàn)，即是否有兩個(gè)同性的昆蟲(chóng)發(fā)生交SampleInput3121413SampleScenarioSuspiciousbugsScenarioNosuspiciousbugs次，說(shuō)明是同一個(gè)的，奇數(shù)次則說(shuō)明是異性。怎樣實(shí)現(xiàn)呢？用一個(gè)rel[i]數(shù)組表示i昆蟲(chóng)相對(duì)根節(jié)點(diǎn)的偏移次數(shù)，初始時(shí)rel[i]=0?？紤]第一對(duì)昆蟲(chóng)a和b的關(guān)系，他們的是不一樣的，如果把a(bǔ)作為根，那么rel[b]=1，這樣b到a的rel[b]+rel[a]ab時(shí)，先判斷rel[a]rel[b]rel[a]+rel[b]是偶數(shù)則兩只昆蟲(chóng)是同性，說(shuō)明找到了一對(duì)#includeconstintMAXN=2005;intf[MAXN],rel[MAXN];voidinit(int{for(inti=0;i<=n;{f[i]=}}

=intfind(int{if(x!={intt=f[x]=rel[x]=(rel[x]+rel[t])%}return}voidunion_set(inta,intb)//a,baredifferent{intfa=find(a),fb=find(b);if(fa!=fb){f[fb]=rel[fb]=(rel[a]-rel[b]+1+2)%}}int{intcaseN;scanf("%d",&caseN);for(intcs=1;cs<=caseN;cs++)intn,boolfound=false;scanf("%d%d",&n,&m);for(inti=0,a,b;i<m;{scanf("%d%d",&a,intta=find(a),tb=find(b);if(ta!=tb){}elseif(rel[a]=={found=}}

printf("%s\n",found?"Suspiciousbugsfound!":"Nosuspiciousif(cs<{}}return}POJ1182A,B,C，這三類(lèi)動(dòng)物的食物鏈構(gòu)成了有趣的環(huán)形。ABBC，CAN1－NA,B,C中的一種，但是我們并不知道它第一種說(shuō)法是"1XY"，表示XY是同類(lèi)。NKK句話有的是真的，有的是。當(dāng)一句話滿足下列三條之一時(shí)，這句話就是假話，否則就是真話。N（1N50,000）K句話（0K100,000，輸出KD，X，YD表示說(shuō)法若D=2，則表示X吃Y。Sample1001101212223112315SampleOutput思路：這一題的基本思路是對(duì)每句話判斷真假，同時(shí)記錄由真話構(gòu)成的食物鏈的結(jié)構(gòu)，進(jìn)行統(tǒng)計(jì)，最后輸出統(tǒng)計(jì)結(jié)果。3個(gè)物種之間的關(guān)系是相對(duì)的，對(duì)稱(chēng)的，所以要記錄的是動(dòng)物間的關(guān)系，而aA，bBa，bA，B就需要合并為一個(gè)集利用并查集來(lái)已知的捕食結(jié)構(gòu)。當(dāng)f[a]=a時(shí)，表示a是本集合的根結(jié)點(diǎn)，f[a]=b表示a，b間有已經(jīng)確定的捕食關(guān)系。這樣想知道a，b間的捕食關(guān)系只要找到a，b的根結(jié)點(diǎn)即可，a，ba，b關(guān)系，a，b有不同根節(jié)點(diǎn)，說(shuō)明a，b關(guān)系尚未確定。這樣我們還需要一個(gè)和f[n]對(duì)應(yīng)的結(jié)構(gòu)vec[n]用以f[a]與其我們以vec[a]=0表示a結(jié)點(diǎn)與其父結(jié)點(diǎn)是同類(lèi)，vec[a]=-1表示a捕食其父結(jié)點(diǎn)，vec[a]=1agetf(a)agetv(a)來(lái)得到a與其根結(jié)點(diǎn)的關(guān)系向量。dababd-1==getv(b)-getv(a)時(shí)同樣，a，b有不同根結(jié)點(diǎn)時(shí)，這句話為真，可以確定兩根結(jié)點(diǎn)的關(guān)系，ab的關(guān)系參考 pa數(shù)組表示每個(gè)節(jié)點(diǎn)的父節(jié)點(diǎn)，ch數(shù)組表示節(jié)點(diǎn)與它的父節(jié)點(diǎn)#include<stdio.h>#include<string.h>constintMAXN=50005;intpa[MAXN],ch[MAXN];intn,k,lies;void{intfor(i=0;i<MAXN;i++)pa[i]=i;memset(ch,0,sizeof(int)*MAXN);lies=}intfind_set(int{if(pa[x]==x)returnx;intxt=ch[x]=(ch[x]+ch[pa[x]]+3)%3;pa[x]=xt;return}voidunion_set(intdintxinty)//d,xy的關(guān)系，01，x吃{if(x>n||y>n)}intfx=find_set(x);intfy=find_set(y);if(fx==fy){if((ch[x]-ch[y]+3)%3!=d)}}elsech[fx]=(d+ch[y]-ch[x]+6)%3;pa[fx]=fy;}}int{inti,d,x,y;scanf("%d%d\n",&n,&k);for(i=0;i<k;i++)scanf("%d%d%d\n",&d,&x,&y);union_set(d-1,x,y);}printf("%d",lies);return0;}HDU1213_HowManyTablesPOJ1703_FindthemCatchthemHrbustoj1418夏夜星空POJ1988Cube 編寫(xiě)：校核：二叉二叉堆(BiaryHeap)是一種特殊的堆，二叉堆是完全二叉樹(shù)或者是近似完全二叉樹(shù)。二叉堆滿足堆特性：父結(jié)點(diǎn)的鍵值總是大于或等于（小于或等于）任何一個(gè)子節(jié)點(diǎn)的鍵值，且每個(gè)結(jié)點(diǎn)的左和右都是一個(gè)二叉堆（都是最大堆或最小堆。當(dāng)父結(jié)點(diǎn)的鍵值總是大于或等于任何一個(gè)子節(jié)點(diǎn)的鍵值時(shí)為最大堆。當(dāng)父結(jié)點(diǎn)的鍵(注:一般把二叉堆簡(jiǎn)稱(chēng)為堆預(yù)備知識(shí)：一棵二叉樹(shù)從上到下，從左到右編號(hào)，我們可以發(fā)現(xiàn)，第i個(gè)節(jié)點(diǎn)的兩個(gè)兒子的編號(hào)分別為2*i，2*i+1。(1)a[i]<=a[i*2]a[i]<=a[i*2+1](即小根堆，節(jié)點(diǎn)的值不大于兩個(gè)兒子的值)(2)a[i]>=a[i*2]a[i]>=a[i*2+1](即大根堆，節(jié)點(diǎn)的值不小于兩個(gè)兒子的值)①堆中任一亦是堆二叉堆的基本元素。使用n表示隊(duì)中元素的個(gè)數(shù)。1、向堆插入一個(gè)結(jié)點(diǎn)(上升操作在堆尾（a[n]）插入一個(gè)元素，然后不斷和父結(jié)點(diǎn)（a[i/2]）Cvoidpush_heap(inta[],int{inti=n;intx=a[n];while(i>1&&a[i/2]<{a[i]=a[i/2];i/=2;}a[i]=}(以上代碼是大根堆的上升操作，小根堆只需將a[i]>a[j]改為a[i]<a[j]即可push_heap函數(shù)進(jìn)行調(diào)整。如下a[n]=x;push_heap(a,刪除堆頂結(jié)點(diǎn)(下降操作（小根堆）再與節(jié)點(diǎn)進(jìn)行比較大小，交換，更換節(jié)點(diǎn)編號(hào)，如此重復(fù)，直到滿足堆的性質(zhì)。C

intnintmn是數(shù)組下標(biāo)范圍，mwhile(m*2<={m=m*if(m<n&&a[m]<{}if(a[m]>a[m/2]){t=a[m];a[m]=a[m/2];a[m/2]=t;}}}

voidpop_heap(inta[],intn){intx;x=a[1];a[1]=a[n];a[n]=x;n--}

n,(以上代碼是大根堆的下降操作，小根堆只需將所有的‘>'換為'<'即可不難得出，兩個(gè)操作的復(fù)雜度都是O(log2N)堆頂元素時(shí)使用的heap函數(shù)進(jìn)行調(diào)整。a[1..n-1]a[n]a[1..n-1]≤a[n]然后再次將a[1..n-1]中關(guān)鍵字最大的記錄a[1]和該區(qū)間的最后一個(gè)記錄a[n-1]交換，由a[1..n-2]a[n-1..n]a[1..n-2]≤R[n-1..n]，同樣要a[1..n-2]調(diào)整為堆。重復(fù)②③的步驟，直到無(wú)序區(qū)只有一個(gè)元素為止，此時(shí)a[1..n]C//首先建堆，從最底層的元素開(kāi)始建堆，一直遞推到堆頂，即下標(biāo)為1的數(shù)據(jù)元

intn)}

(i=n/2;i>0;--i)heap(a,n,voidheadp_sort(inta[],intn){inti;for(i=n;i>1;--i){intt=a[1];a[1]=a[i];a[i]=t;heap(a,n-i,}}經(jīng)典poj3253Fence少需要？N(1N20000)Ni+1行一個(gè)整Li（1≤Li≤50000i根模木板。每次只取兩根長(zhǎng)度最小的木板，然后連接成一根木板，放入剩余的木板集合中，然后重復(fù)上述過(guò)程，知道剩余木板集合中只剩下一根木板，每次連接木板的花費(fèi)的和就是#include<stdio.h>#include<string.h>constintmaxnintl[maxn];intn,h,min;longlong

{

intlg,lr,t;while((x<<1)<=h){lg=x<<1;lr=(x<<1)+1;if(lr<=h&&l[lg]lg=lr;if(l[x]l[lg]){tl[x]=l[lg];l[lg]=t;x=

>}}}int{intwhile(1==&n)){for(i=1;i<=n;h=for(i=n/2;i>0;i--)ans=0;while(h>1){min=l[1];l[1]=l[h];h--;min+=l[1];l[1]=min;ans+=}}return}POJ2442題意：有m個(gè)序列，每個(gè)序列n個(gè)非負(fù)數(shù)，從每個(gè)序列中選擇一個(gè)數(shù)組成一個(gè)序列并計(jì)算和，總共有nm個(gè)和，輸出最小的n個(gè)和。思路：直接計(jì)算復(fù)雜度太高。故考慮類(lèi)似動(dòng)態(tài)規(guī)劃的思想。先求出前k-1個(gè)序列的最nA數(shù)組中，Ak-1k序列的數(shù)B數(shù)組，Bk個(gè)數(shù)和，Bnkli1<=i<=n)ABB數(shù)組中的最小的n個(gè)元素。ABC++STL庫(kù)#include<cstdio>#include<algorithm>usingnamespaceconstintMAXN=2005,MAXM=105;inta[2][MAXN];int{intruns;while(runs--){intn,m;scanf("%d%d",&m,&n);for(inti=0;i<n;++i)scanf("%d",a[0]+i);make_heap(a[0],a[0]+n);intq=for(intint

=1;h<m;++h,q=1-q)for(inti=0;i<n;++i)a[1-q][i]=a[q][i]+t;for(inti=1;i<n;++i){for(intj=0;j<n;{intt2=a[q][j]+if(t2<a[1-q][0])pop_heap(a[1-q],a[1-q]+n);a[1-q][n-1]=t2;push_heap(a[1-}}}}

a[1-q]+sort(a[q],a[q]+for(inti=0;i<n-1;++i){printf("%d",a[q][i]);}}return}POJ MooUniversity-FinancialN元子集，使得其中位數(shù)最大，而資費(fèi)總和<=f（特定的值）思路：先將牛以score從小到大排序。于是可以枚舉[N/2..C-N/2]之間的每頭牛為中位數(shù)點(diǎn)，那么要滿足題目條件ii點(diǎn)之前的(n/2)financialaidii點(diǎn)之后的(n/2)financialaidafter[i]ifa[i](ifinancialaid值）before[i]afeter[i]Fscore遞增的，從大到小掃一遍，遇到的第一個(gè)結(jié)果就是答案，時(shí)間復(fù)雜度O(n)。分別一個(gè)大根堆，初始的時(shí)候最大堆的元素的數(shù)目為(n/2)個(gè)，那么每次更新一頭牛i的時(shí)候，若這個(gè)點(diǎn)的fa[i]>大根堆堆頂點(diǎn)的fa，那么更新before[]（afeter[]）值即于是只需要log(n)的時(shí)間來(lái)這個(gè)before[i]/after[i]值，故總的復(fù)雜度為O(Nlog2N)#include<cstdio>#include<cstring>#include<iostream>usingnamespaceconstintMAXN=100000+100;structNode{ints,booloperator<(constNode&B)const}

s<}intbefore[MAXN];intheap[MAXN];intheap_size,voidadjust(int{int*p=heap-1;intval=p[c];while(c*2<=heap_size)intlc=c*if(lc<heap_size&&p[lc+1]>p[lc])}if(p[lc]>val)p[c]=p[lc];c=lc;}else}}p[c]=}voidinit_heap(intl,int{heap_sum=}

(inti=l;i<=r;{heap[i-l]=node[i].f;heap_sum+=node[i].f;for(inti=heap_size/2;i>0;--{}}{int*p=heap-1;if(f<p[1]){heap_sum-=p[1]-p[1]=}}int{intn,c,while(EOF!=scanf("%d%d%d",&n,&c,{for(inti=0;i<c;++i)scanf("%d%d",&node[i].s,}sort(node,node+c);heap_size=n/2;init_heap(0,heap_size-1);for(inti=heap_size;i<c-heap_size;++i){before[i]=heap_sum;}intans=-init_heap(c-heap_size,c-for(inti=c-heap_size-1;i>=heap_size;--{intt=before[i]+heap_sum+node[i].f;if(0<=t&&t<=f){ans=}}}return}POJ3481DoubleK標(biāo)識(shí)，戶提供一個(gè)優(yōu)先級(jí)P，根據(jù)優(yōu)先級(jí)來(lái)確定先處理哪個(gè)用戶的業(yè)務(wù)，并且有時(shí)候是優(yōu)先級(jí)高01K23每一行為一個(gè)請(qǐng)求，并且最后一行的請(qǐng)求為0，表示停止服務(wù)。輸入保證有類(lèi)型為

P小 23的請(qǐng)求，輸出服務(wù)的客戶標(biāo)識(shí)。如果沒(méi)有客戶在請(qǐng)求，則輸0。POJ3481Double#include<cstdio>#include<cstring>#include<utility>#include<algorithm>usingnamespacetypedefpair<int,int>constintMAXN= structKP{intval,id;intfix;structgreaterKPbooloperator()(constKP&a,constKP&b){returna.val>}structlessKPbooloperator()(constKP&a,constKP&b){returna.val<} booldel[MAXN];intsz_max,sz_min;KPkp_max[MAXN],template<classintget(KPa[],int&sz){while(sz>0&&del[a[0].fix]){pop_heap(a,a+sz,--}if(sz==0)return0;else{del[a[0].fix]=1;returna[0].id;}}template<classvoidins(KPa[],int&sz,constKP{a[sz++]=tmp;push_heap(a,a+sz,cmp());}voidinit()sz_max=sz_min=0;t=0;}int{intwhile(EOF!=scanf("%d",{if(cmd==0){}if(cmd==1)intk,p;scanf("%d%d",&k,&p);KPt;t.val=p;t.id=k;t.fix t; =0;ins<lessKP>(kp_max,sz_max,}elseif(cmd==2)inta=get<lessKP>(kp_max,sz_max);printf("%d\n",a);}elseif(cmd==3)inta=get<greaterKP>(kp_min,sz_min);printf("%d\n",a);}else}}return}POJ3481DoubleQueuePOJ1442BlackBox 編寫(xiě)：校核：基本O(N)的時(shí)間復(fù)雜度，如這個(gè)需求非常的頻繁，那么這個(gè)操作就會(huì)占用大量的CPU時(shí)間，進(jìn)一步想，你有可能會(huì)想到使用空間換取時(shí)間的方法，把每一段區(qū)間的值一次記錄下來(lái)，然后在內(nèi)存中，將時(shí)間復(fù)雜度降低到O（1），但若是我們的源數(shù)據(jù)需要頻繁的更改怎么辦？使用上面的方案，我們需要大量的更新我們保存到內(nèi)存中的區(qū)間和，而且這中間的很多更新的影響是的，我們需要重復(fù)計(jì)r[array[4]值，需要更新區(qū)間[在更新[]需要又一次的計(jì)算[]，這樣的更新帶來(lái)了非常多的重復(fù)計(jì)算，為了解決這一問(wèn)題，樹(shù)狀數(shù)組應(yīng)運(yùn)而生了。當(dāng)要頻繁的對(duì)數(shù)組元素進(jìn)行修改,同時(shí)又要頻繁的查詢數(shù)組內(nèi)任一區(qū)間元和的時(shí)候,可以考慮使用樹(shù)狀數(shù)組.樹(shù)狀數(shù)組是一種非常優(yōu)雅的數(shù)據(jù)結(jié)構(gòu).先來(lái)看看一張樹(shù)狀結(jié)構(gòu)的圖片：圖中C[1]的值等于A[1]，C[2]的值等于C[1]+A[2]=A[1]+a[2],C[4]數(shù)組中的元素有c[2],c[4],c[8],我們只需要重新計(jì)算這幾個(gè)值即可，減少了很多重復(fù)的操下面看看它的定義：假設(shè)a[1...N]為原數(shù)組,定義c[1...N]為對(duì)應(yīng)的樹(shù)狀c[i]a[i2^k1]a[i2^k2]a[i]（ki0數(shù)了我們C數(shù)組的正確意義，至于證明過(guò)程，請(qǐng)讀者自己查找資料。就是前一位的權(quán)值,0100中,2^2=41的權(quán)值.2^k可以表示為n&(n^(n-1))或更簡(jiǎn)單的n&(-n)，例如：inti=3&(-3);i=1，30011,-31101(負(fù)數(shù)存的是補(bǔ)碼）所以0011&1101=1intj=4&(-4); j=4，理由同上。所以計(jì)算2^k我們可以用如下代碼：intlowbit(intx)//lowbit{returnx&(-x)returnx&x^x}這個(gè)操作的時(shí)間復(fù)雜度是O(1)么，請(qǐng)見(jiàn)代碼i-=lowbit(i)注釋{ints=0;{s+=i-=}return}時(shí)間復(fù)雜度是O(logN)代碼中“ilowbit(i)i1剪去，再向前數(shù)當(dāng)前1的權(quán)個(gè)數(shù)（例子在下面，而n的二進(jìn)制里最多有l(wèi)og(n)個(gè)1，所以查詢效率是log(n)，在示意圖上的操作即可理解為依次找到所有的子節(jié)點(diǎn)。sum[1..7]為例,0111,10位上,a[7]開(kāi)始向前數(shù)1個(gè)元素(只有a[7]),即c[7];1舍掉,6,0110,11位上,也就是說(shuō)要從a[6]開(kāi)始向前數(shù)2個(gè)元素(a[6],a[5]),即c[6];然后舍掉用過(guò)的1,得到4,二進(jìn)制表示為0100,右邊第一個(gè)1出現(xiàn)在第2位上,也就是說(shuō)要從a[4]開(kāi)始向前數(shù)4個(gè)元素(a[4],a[3],a[2],a[1]),即c[4].所以s[7]=c[7]+c[6]+c[4]a[2],c數(shù)組中的元素有{

add(inti,int{c[i]+=i+=}}時(shí)間復(fù)雜度是O(logN)代碼中“ilowbit(i)i+（i1的權(quán)值,2^k）,在示意圖以修a[2]元素為例，需要修改c[2],2的二進(jìn)制為0010,末尾補(bǔ)00100,c[4]，4的010001000c[8]。所以我們需要修改的有c[2],c[4],c[8]。樹(shù)狀POJ2352如果一個(gè)星星的左下方（包含正左和正下)kk級(jí)的.比如，在下面的例圖中，星星53級(jí)的（1，2，4在它左下。2，4110級(jí)，21級(jí)，12級(jí)，13 每個(gè)星星的級(jí)別定義就是在它的左下角有多少顆星星，我們可以先對(duì)Y排序,然后就X比他小的又多少個(gè)，這樣就能算出星星的級(jí)別了，這需要樹(shù)狀數(shù)組。從這里我們可以看出，樹(shù)狀數(shù)組的是某一段范圍內(nèi)有多少個(gè)點(diǎn)。C++（下面的代碼只是利用了樹(shù)狀數(shù)組的知識(shí)，并沒(méi)有把相應(yīng)的add和sum函數(shù)#include<stdio.h>#include<string.h>constintMAXN=15000+5;constintMAXXY=32000;intlevel[MAXN];intf[MAXXY*3+3];intint{while(EOF!=scanf("%d",{memset(level,0,sizeof(level));memset(f,0,sizeof(f));for(inti=0;i<n;i++)intx,y,s=0,k=1,l=0,r=MAXXY;scanf("%d%d",&x,&y);while(l<r)intmid=(r-l)/2+l;if(mid<x){//rightl=mid+1;s+=f[k];k=(k<<1)+}else{//leftr=mid;k<<=}}s+=}for(inti=0;i<n;{}}return}hrbustoj1400XianGe非常喜歡比賽尤其是像達(dá)喀爾拉力賽，這種的比賽規(guī)模很大，涉及到很多國(guó)家的車(chē)隊(duì)的許多車(chē)手參賽。XianGe也夢(mèng)想著自己能舉辦一個(gè)這樣大規(guī)模的比賽，XianGe幻想著有許多人參賽，那是人山人海啊，不過(guò)XianGe只允許最多100000人參這么大規(guī)模的比賽應(yīng)該有技術(shù)統(tǒng)計(jì)，在XianGe

個(gè)數(shù)據(jù)，車(chē)輛起始位置Xi和速度Vi（0<Xi,Vi< 為i的車(chē)，它肯定是會(huì)被位置比i小，速度快的車(chē)超過(guò)，我們用樹(shù)狀數(shù)組統(tǒng)計(jì)出車(chē)速?gòu)?到車(chē)i的速度vi之間有多少量車(chē)s，因?yàn)楫?dāng)前統(tǒng)計(jì)了多少量車(chē)已經(jīng)知道，即位置為i的車(chē)就是加入統(tǒng)計(jì)的第i量車(chē)，有i-s量車(chē)會(huì)超過(guò)車(chē)i，統(tǒng)計(jì)后輸出這個(gè)結(jié)果即可。#include<stdio.h>#include<string.h>#include<stdlib.h>#defineDATSIZ100005typedef{intx,CARintintcmp(constvoid*a,constvoid*{CAR*c=(CAR*)a;CAR*d=if(c->x==d->x)returnd->v-c-returnc->x-d-}voidupdate(intbit[],intpos,{

dt,intintfor(i=pos;i<=nMax;i+=lowbit(i)){bit[i]+=dt;}}intgetsum(intbit[],int{intres=0;while(pos>0){res+=bit[pos];pos-=lowbit(pos);}return}int{intn,i,nMax;longlongsum;while(scanf("%d",&n)!={memset(bit,0,nMax=0;for(i=1;i<=n;i++)if(nMax<}

nMax=qsort(car+1,n,sizeof(car[0]),cmp);sum=0;for(i=1;i<=n;i++){update(bit,car[i].v,1,nMax);sum+=i-getsum(bit,car[i].v);}}return}hrbustoj1161Leyni擄走，身在水深火熱之中小奈葉為了拯救Leyni，獨(dú)自一人前往森林深處從靜竹手中奪回中的Leyni。這個(gè)保護(hù)圈由n個(gè)小的小護(hù)盾?chē)梢蝗Γ瑥?到n編號(hào)。當(dāng)某一塊小護(hù)盾受到的時(shí)候，小護(hù)盾就會(huì)抵消掉這次，也就是說(shuō)對(duì)這一塊小護(hù)盾的是無(wú)效，從而保護(hù)圈里的人，不過(guò)小護(hù)盾在遭到一次后，需要t秒進(jìn)行冷卻，在冷卻期間受到的都是有效,此時(shí)他們就會(huì)遭到，即假設(shè)1秒時(shí)受到并成功防御，到1+t秒時(shí)冷卻才結(jié)束并能進(jìn)行防御，在2到t受到的都是有效?，F(xiàn)在小奈葉專(zhuān)心戰(zhàn)斗，Leyni，他們無(wú)法得知小護(hù)盾的有效次數(shù)，他們第一行是一個(gè)整數(shù)T第一行是三個(gè)整數(shù)，n,q,t，n表示保護(hù)圈的長(zhǎng)度，q表示的詢問(wèn)的總次數(shù)，tAttackQuerya

1<=a<=ab

的小護(hù)盾(包括a和b)總共受到了多少次有效。保第k次發(fā)生在第k秒，詢問(wèn)不花費(fèi)時(shí)間1<=n,q1t50每一組測(cè)試數(shù)據(jù)，先輸出一行"Casei:",i表示第i組測(cè)試數(shù)據(jù)，從1開(kāi)始計(jì)數(shù)。題目要對(duì)每個(gè)查詢輸出某個(gè)護(hù)盾承受了多少次的有效，即沒(méi)有保護(hù)罩的時(shí)候。因?yàn)槊總€(gè)護(hù)盾有冷卻時(shí)間，冷卻時(shí)間內(nèi)的都是有效，我們用一個(gè)樹(shù)狀數(shù)組統(tǒng)計(jì)護(hù)盾受到的次數(shù)；還要記錄每個(gè)護(hù)盾的最后開(kāi)始冷卻時(shí)間，也就是最后一次成功防御的時(shí)間，每次某快護(hù)盾的時(shí)候，先檢查這塊護(hù)盾的冷卻時(shí)間，如果冷卻時(shí)間已經(jīng)過(guò)了，說(shuō)明可以承受這次，如果冷卻時(shí)間沒(méi)過(guò)，則受到一次有效。#include<stdio.h>#include<string.h>constintmaxn=100000;constintmaxt=50;intc[maxn+1];intn,q,t;intp[maxn+1];inlineintlowbit(int{return(x)&(-}intinit()memset(c,0,}voidadd(intx,int{inti=for(;x<=n;x+={c[x]+=}}intgetSum(int{ints=for(;x>0;x-={s+=}return}int{intCase,T;charcmd[16]; inti,a,for(Case=1;Case<=T;{scanf("%d%d%d",&n,&q,//printf("%d%d%d\n",n,q,t);for(i=0;i<=n;++i){p[i]=-}printf("Case%d:\n",Case);t=for(i=0;i<q;++i){scanf("%s",cmd);if(cmd[0]== scanf("%d",if(p[a]+t {p[a] }elseadd(a,}}elseif(cmd[0]==scanf("%d%d",&a,&b);if(a>b){intt=a=b=}}}}return}其他POJ2085POJ1195Mobilehrbustoj1451 編寫(xiě)：盧俊 校核：線段此時(shí)可以在結(jié)點(diǎn)結(jié)構(gòu)中加入一個(gè)變量intcount；代表當(dāng)前結(jié)點(diǎn)代表的中被覆蓋的線段長(zhǎng)度和。這樣就要在插入（刪除）當(dāng)中這個(gè)count值，于是當(dāng)前的覆蓋總值就是根節(jié)點(diǎn)的count值了。延遲標(biāo)記的作用是延遲對(duì)子區(qū)間的更新，優(yōu)點(diǎn)是更新操作不必“進(jìn)行到底”。例如將線段#defineMAXSIZE200000intval[MAXSIZE+1];structnode{intmax;intleft;intright;intmax(intx,int{return}intcreate(introot,intleft,int//以root{tree[root]right=right;returntree[root]max=val[left];inta,b,middle=(left+right)/2;returntree[root].max=max(a,b);}intcalculate(introot,intleft,int//以root為根節(jié)點(diǎn)的線段樹(shù)中，求取區(qū)間[left,right]{if(tree[root].left>right||tree[root]right<left)return0;if(left<=tree[root].left&&tree[root]right<=right)returntree[root]max;inta,b;returnmax(a,b);}intupdata(introot,intpos,int//以root為根節(jié)點(diǎn)的線段樹(shù)中，將位置pos的元素更新為val{if(pos<tree[root].left||tree[root]right<pos)returntree[root]max;if(tree[root].left==pos&&tree[root]right==pos)returntree[root]max=val;returntree[root].max=max(a,b);}經(jīng)典HDU1754IHate[HDU][1754][線段樹(shù)IHateItmax用于記錄該節(jié)點(diǎn)所表示區(qū)間的最大值。更新和查詢操作均返代碼（CourierNew字體，小五號(hào)，間距為固定值12磅）#include<stdioh>usingnamespacestd;#defineMAXSIZE200000intval[MAXSIZE+1];structnode{intmax;intleft;intright;intmax(intx,int{return}intcreate(introot,intleft,int//以root{tree[root]right=right;returntree[root]max=val[left];inta,b,middle=(left+right)/2;returntree[root].max=max(a,b);}intcalculate(introot,intleft,int//以root為根節(jié)點(diǎn)的線段樹(shù)中，求取區(qū)間[left,right]{if(tree[root].left>right||tree[root]right<left)return0;if(left<=tree[root].left&&tree[root]right<=right)returntree[root]max;inta,b;returnmax(a,b);}intupdata(introot,intpos,int//以root為根節(jié)點(diǎn)的線段樹(shù)中，將位置pos的元素更新為val{if(pos<tree[root].left||tree[root]right<pos)returntree[root]max;if(tree[root].left==pos&&tree[root]right==pos)returntree[root]max=val;returntree[root].max=max(a,b);}int{intn,m;{for(inti=1;i<=n;i++)for(int{charop;inta,b;}}}

思考與擴(kuò)展：可以借鑒培訓(xùn)中做法HDU1698Justa[HDU][1698][線段樹(shù)JustaHook作將區(qū)間[x,y]上的值更新為z。所有操作結(jié)束后，求出序列的總和。12磅#include<stdioh>intval[MAXSIZE+1];structnode{

CourierNewintintleft;intright;intintcreate(introot,intleft,int//以root{tree[root]mark=0;tree[root]right=right;returntree[root].total=val[left];intmiddle=(left+right)/2;return}voidupdata_mark(int//更新root{{tree[root].total=tree[root]mark*(tree[root]right-tree[root].left+1);if(tree[root].left!=tree[root]right)tree[root*2]mark=tree[root*2+1]mark=tree[root]mark;tree[root]mark=0;}}intcalculate(introot,intleft,int//以root為根節(jié)點(diǎn)的線段樹(shù)中，求取區(qū)間[left,right]{if(tree[root].left>right||tree[root]right<left)return0;if(left<=tree[root].left&&tree[root]right<=right)returnreturn}intupdata(introot,intleft,intright,int//以root為根節(jié)點(diǎn)的線段樹(shù)中，將區(qū)間[left,right]中的元素更新為val{if(tree[root].left>right||tree[root]right<left)returntree[root].total;if(left<=tree[root].left&&tree[root]right<=right){tree[root]returntree[root].total=val*(tree[root]right-}return}int{intt;for(int{for(intj=1;j<=n;j++)for(int{}printf("Case%d:Thetotalvalueofthehookis}}思考與擴(kuò)展：可以借鑒培訓(xùn)中做法POJ3468ASimpleProblemwith[POJ][3468][線段樹(shù)ASimpleProblemwithIntegersupdata_mark()操作，意在更新當(dāng)前節(jié)點(diǎn)，因?yàn)楦虏僮餍枰祷禺?dāng)前節(jié)點(diǎn)的信息。代碼（包含必要注釋?zhuān)捎米钸m宜閱讀的CourierNew字體，小五號(hào)，間距為固定值12磅）#include<stdioh>usingnamespacestd;#defineMAXSIZEintstruct{longlongintleft;intlonglonglonglongcreate(introot,intleft,int//以root{tree[root]mark=0;tree[root]right=right;returntree[root].total=val[left];intmiddle=(left+right)/2;return}voidupdata_mark(int//更新root{{tree[root].total+=tree[root]mark*(tree[root]right-tree[root].left+1);if(tree[root].left!=tree[root]right){tree[root*2]mark+=tree[root]mark;tree[root*2+1]mark+=tree[root]mark;}tree[root]}}longlongcalculate(introot,intleft,int//以root為根節(jié)點(diǎn)的線段樹(shù)中，求取區(qū)間[left,right]{if(tree[root].left>right||tree[root]right<left)return0;if(left<=tree[root].left&&tree[root]right<=right)returnreturn}longlongupdata(introot,intleft,intright,int//以root為根節(jié)點(diǎn)的線段樹(shù)中，將區(qū)間[left,right]中的元素加上val{if(tree[root].left>right||tree[root]right<left)returntree[root].total;if(left<=tree[root].left&&tree[root]right<=right){tree[root]mark+=val;returntree[root].total;}return}int{intn,q;{for(inti=1;i<=n;i++)charop;for(int{{}{}}}}

inta,b;inta,b,c;思考與擴(kuò)展：可以借鑒培訓(xùn)中做法POJ3832[POJ][3832][線段樹(shù)Posters現(xiàn)在有n個(gè)不同大小的“回型”圖案，他們可能互相，請(qǐng)求出被他們所覆蓋的平xx軸距離，tree[1].len代碼（CourierNew字體，小五號(hào)，間距為固定值12磅）#include<stdioh>usingnamespacestd;#defineMAXSIZE#defineN50000structnode{intintleft;intright;intlen;struct{int//pos表示yintleft;intright;boolint//一共total_edge個(gè)線段，nvoidcreate(introot,intleft,int{tree[root]right=right;re