noip相关各种区间第大值

C++ext/pb_dsOctober31,2012运行环 Basic 区间第K大 树的合 树的分 Trie搜索前 重复元素的插 Priority 优先队列的合 优先队列内部元素的修 TSg++g++(Ubuntu4.4.3-4ubuntu5.1)Copyright(C)2009SoftwareFoundation,Thisissoftware;seethesourceforcopyingconditions. ThereisNOwarranty;notevenforMERCHANTABILITYorFITNESSFORAPARTICULAR更高版本的g++的ext/pb_ds稍有更改，如果不能编译，请到ext/pb_ds Basicpb_dspb_dsSTLstd::mapstd::set BASIC在pb_dsstd::mapmap的内部结构实现，sov_treta（ordeedecorb_tree_tag性能更好。下面这段代码展示 gnu_pbds::tree的基本用##include<cstdio>#include<string>#includeusingnamespaceusingnamespacetypedeftree<string,int,less<string>,rb_tree_tag>Tree;intmain(){Treet["abc"]=t["basicmap"]=assert(t.find("basicmap")!=t.end());fortori=t.begin();i!=t.end();{printf("%s%d\n",i−>first.c_str(),}}注意typedef中的null_mapped_type，在新版本的实现中变为了null_type，具体可以在ex-t/pb_ds/tag_and_trait.hpp中找到##include<cstdio>#include<string>#includeusingnamespaceusingnamespacetypedeftree<string,null_mapped_type,less<string>,rb_tree_tag>Tree;intmain(){Treeassert(t.find("basicmap")!=t.end());fortori=t.begin();i!=t.end();{printf("%s\n",}}Tree-LikeContainers(TreesandKpb_ds中的treeK大的元素是多少，并且可以查询一个给inlineconst_itorfind_by_order(size_typeorder)constinlineitorfind_by_order(size_typeorder)inlinesize_typeorder_of_key(const_key_referencer_key)其中find_by_order的作用是查找第order大的元素并返回指向它的迭代器order_of_key的作r_key0开始。#include#include#include<ext/pb_ds/tree_ usingnamespaceusingnamespacetypedeftree<int,null_mapped_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>set_t;int{set_tassert(*s.find_by_order(5)==10000);assert(s.find_by_order(6)==s.end());assert(s.order_of_key(10000)==5); )==6);assert(*s.find_by_order(4)==10000);assert(s.find_by_order(5)==s.end());assert(s.order_of_key(100000)==5); )==5);}##include<cstdio>#include<ext/pb_ds/exception.hpp>#include<cassert>usingnamespaceusingnamespacetypedeftree<int,char,less<int>,rb_tree_tag>map_t;intmain(){map_th0,for(inti0=0;i0<100;++i0)for(inti1=0;i1<100;++i1)h1.insert(make_pair(1000+i1,'b'));//Checkthath0shouldnowcontainallentries,andh1shouldbeempty.assert(h0.size()==200);map_th2,h3;h2[1]='a';h2[3]=h3[2]=//Nowperformanillegal//Itisnottruethatallelementsinh2aresmallerthanthose//h3,norisittruethattheyarealllarger.Hence,attempting//joinh2,andh3shouldresultinanexception.boolexception_thrown=false;try}catch(gnu_pbds::join_error&{exception_thrown=}//Sincetheoperationwasnotperformed,thetablesshouldbeunaltered.assert(h2.size()==2);assert(h3[2]==return}##include<string>#includeusingnamespaceusingnamespaceint{//APATRICIAtrietablestringstotypedeftrie<string,char>//Amap_typeobject.map_typer;//Insertssomeentriesintor.for(inti=0;i<100;++i)//Nowsplitrintoadifferentmap_type//larger_rwillholdthelargervaluesfollowingthesplit.map_typelarger_r;////Splitallelementswithkeylargerthan'a'^1000into//Thisisexception r.split(string(1000,'a'),larger_r);//Sincetherewerenoelementswithkeylargerthan'a'^1000,//shouldbeunchanged.assert(r.size()==100);//Nowperformasplitwhichactuallychangesthecontentof//Splitallelementswithkeylargerthan"aaa"intolarger_r.r.split(string("aaa"),larger_r);assert(r.size()==4);assert(larger_r.begin()−>first==string("aaaa"));return}#include<cassert>#include<ext/pb_ds/trie_ #include<ext/pb_ds/tag_and_trait.hpp>#include<string>usingnamespaceusing typedeftrie<string,null_mapped_type,string_trie_e_access_traits<>,pat_trie_tag,trie_prefix_search_node_update>trie_type;//Thefollowinghelperfunctiontakesatrieobjectandr_key,//constreferencetoastring,andprintsallentrieswhose//includesr_keyasavoidprint_prefix_match(consttrie_type&t,conststring&key)cout<<"Allkeyswhoseprefixmatches\""<<key<<"\":"<<endl; tor,trie_type::const_i tor>match_range=for(trie_type::const_i torit=match_range.first;it!=match_range.second;++it)cout<<*it<<'';cout<<endl;}int{trie_type//Insertsomeentries.assert(t.insert("I").second==true);assert(t.insert("wish").second==true);assert(t.insert("that").second==true);assert(t.insert("I").second==false);assertassert(t.insert("could").second==true);assert(t.insert("ever").second==true);assert(t.insert("see").second==true);assert(t.insert("a").second==true);assert(t.insert("poem").second==true);assert(t.insert("lovely").second==true);assert(t.insert("as").second==true);assert(t.insert("a").second==false);assert(t.insert("trie").second==true);//Nowsearchforprefixes.print_prefix_match(t,"");print_prefix_match(t,"a");print_prefix_match(t,"as");print_prefix_match(t,"ad");print_prefix_match(t,"t");print_prefix_match(t,"tr");print_prefix_match(t,"zzz");return}VijosP1081#include<iostream>#include<cstdio>#include<#include<iostream>#include<cstdio>#include<cstring>#include<cstdlib>#include<ext/pb_ds/tree_ #include<ext/pb_ds/tag_and_trait.hpp>usingnamespaceusingnamespaceconstintkMaxN=100010;constintkMaxM=50050;typedeftree<double,null_mapped_type,less<double>,rb_tree_tag,tree_order_statistics_node_update>Tree;structQuesbooloperator<(constQues&r){if(x!=r.x){returnx<r.x;}elsereturny<}}intx,intk;intn,intans[kMaxN];Treet;voidWork()sort(ques+1,ques+1+intlast_s=0,last_t=0;intorder=0;for(inti=1;i<=m;{intx=ques[i].x;inty=ques[i].y;intk=ques[i].k;intno=ques[i].no;if(x>{t.clear();order=0;for(intj=x;j<=y;{t.insert((double)value[j]+0. *order);}}elsefor(intj=last_s;j<x;{}for(intj=last_t+1;j<=y;{t.insert((double)value[j]+0. *order);}}ans[no]=*t.find_by_order(k−1);last_s=x;last_t=}}intmain()scanf("%d%d",&n,for(inti=1;i<=n;{scanf("%d",}for(inti=1;i<=m;i++)scanf("%d%d%d",&ques[i].x,&ques[i].y,&ques[i].k);ques[i].no=i;}for(inti=1;i<=m;i++)}return}Priority#include<iostream>#include<cassert>#includeusingnamespaceusingnamespaceintmain()for(size_ti=0;i<10;{even_p.push(2*i);odd_p.push(2*i+1);}cout<<"Initialvaluesinevenpriorityqueue:"<<gnu_pbds::priority_queue<int>::const_i torit;for(it=even_p.begin();it!=even_p.end();cout<<*it<<cout<<"Initialvaluesinoddpriorityqueue:"<<endl;for(it=odd_p.begin();it!=odd_p.end();++it)cout<<*it<<endl;cout<<"After−joinvaluesinevenpriorityqueue:"<<endl;for(it=even_p.begin();it!=even_p.end();++it)cout<<*it<<endl;assert(odd_p.size()==0);return}#include<