ACM_JAVA(ACM模板).pdf

《ACM_JAVA(ACM模板).pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、UniversityofTokyo2データ構造1/2513intres=0;1テンプレート14for(inti=t;i>0;i-=i&-i){1importstaticjava.lang.Math.*;15res+=vs[i];2importstaticjava.util.Arrays.*;16}3importjava.io.*;17returnres;4importjava.util.*;18}519//[0,i]の和がkより大きくなる最小のiを求める6publicclassMain{20intget(intk){7staticbo

2、oleanLOCAL=System.getSecurityManager()==null;21intp=Integer.highestOneBit(vs.length-1);8Scannersc=newScanner(System.in);22for(intq=p;q>0;q>>=1,p

3、=q){923if(p>=vs.length

4、

5、k

6、intln(deepToString(os));28}15}162.2RMQ17publicstaticvoidmain(String[]args){1classRMQ{18if(LOCAL){2int[]vs;19try{3int[][]min;20System.setIn(newFileInputStream("in.txt"));4RMQ(int[]vs){21}catch(Throwablee){5intn=vs.length,m=log2(n)+1;22LOCAL=false;6this.vs=vs;23}7min=newi

7、nt[m][n];24}8for(inti=0;i

8、は一番最初のを返す2int[]vs;17intquery(intfrom,intto){3BIT(intn){18intk=log2(to-from);4vs=newint[n+1];19returnvs[min[k][from]]<=vs[min[k][to-(1<

9、Integer.numberOfLeadingZeros(b);9}24}10}25}11intsum(ints,intt){12if(s>0)returnsum(0,t)-sum(0,s);UniversityofTokyo2データ構造2/252.3範囲の更新25if(t==null)returnnewT(key,val,random(),null,null);1classIntervals{26if(key

10、eeMapmap=newTreeMap();27if(key>t.key)returnt.change(t.left,put(t.right,key,val)).normal();3Intervals(){28returnnewT(key,val,t.p,t.left,t.right);4map.put(Integer.MIN_VALUE,-1);29}5map.put(Integer.MAX_VALUE,-1);30Tremove(Tt,intkey){6}31if

11、(t==null)returnnull;7voidpaint(ints,intt,intc){32if(key