mooc数据结构pa

范围查询(Range)DescriptioinLetSbeasetofnintegralpointsonthex-axis.Foreachgiveninterval[a,b],youareaskedtocountthepointslyinginside.InputThefirstlinecontainstwointegers:n(sizeofS)andm(thenumberofqueries).ThesecondlineenumeratesallthenpointsinS.Eachofthefollowingmlinesconsistsoftwointegersaandbanddefinesanqueryinterval[a,b].OutputThenumberofpointsinSlyinginsideeachofthemqueryintervals.ExampleInput5213791146712Output03Restrictions0=n,m=5*10^5Foreachqueryinterval[a,b],itisguaranteedthata=b.PointsinSaredistinctfromeachother.Coordinatesofeachpointaswellasthequeryintervalboundariesaandbarenon-negativeintegersnotgreaterthan10^7.Time:2secMemory:256MB描述数轴上有n个点，对于任一闭区间[a,b]，试计算落在其内的点数。输入第一行包括两个整数：点的总数n，查询的次数m。第二行包含n个数，为各个点的坐标。以下m行，各包含两个整数：查询区间的左、右边界a和b。输出对每次查询，输出落在闭区间[a,b]内点的个数。样例见英文题面限制0≤n,m≤5×105对于次查询的区间[a,b]，都有a≤b各点的坐标互异各点的坐标、查询区间的边界a、b，均为不超过10^7的非负整数时间：2sec内存：256MB祖玛(Zuma)DescriptionLet'splaythegameZuma!Thereareasequenceofbeadsonatrackattherightbeginning.Allthebeadsarecoloredbutnothreeadjacentonesareallowedtobewithasamecolor.Youcantheninsertbeadsonebyoneintothesequence.Oncethree(ormore)beadswithasamecolorbecomeadjacentduetoaninsertion,theywillvanishimmediately.Notethatitispossibleforsuchacasetohappenformorethanonceforasingleinsertion.Youcan'tinsertthenextbeaduntilalltheeliminationshavebeendone.Givenboththeinitialsequenceandtheinsertionseries,youarenowaskedbythefanstoprovideaplaybacktoolforreplayingtheirgames.Inotherwords,thesequenceofbeadsafterallpossibleeliminationsasaresultofeachinsertionshouldbecalculated.InputThefirstlinegivestheinitialbeadsequence.Namely,itisastringofcapitallettersfrom'A'to'Z',wheredifferentletterscorrespondtobeadswithdifferentcolors.Thesecondlinejustconsistsofasingleintergern,i.e.,thenumberofinsertions.Thefollowingnlinestellalltheinsertionsinturn.EachcontainsanintegerkandacapitalletterΣ,givingtherankandthecolorofthenextbeadtobeinsertedrespectively.Specifically,krangesfrom0tomwhentherearecurrentlymbeadsonthetrack.Outputnlinesofcapitalletters,i.e.,theevolutionaryhistoryofthebeadsequence.Specially,-standsforanemptysequence.ExampleInputACCBA51B0A2B4C0AOutputABCCBAAABCCBAAABBCCBA-ARestrictions0=n=10^40=lengthoftheinitialsequence=10^4Time:2secMemory:256MBHintsList描述祖玛是一款曾经风靡全球的游戏，其玩法是：在一条轨道上初始排列着若干个彩色珠子，其中任意三个相邻的珠子不会完全同色。此后，你可以发射珠子到轨道上并加入原有序列中。一旦有三个或更多同色的珠子变成相邻，它们就会立即消失。这类消除现象可能会连锁式发生，其间你将暂时不能发射珠子。开发商最近准备为玩家写一个游戏过程的回放工具。他们已经在游戏内完成了过程记录的功能，而回放功能的实现则委托你来完成。游戏过程的记录中，首先是轨道上初始的珠子序列，然后是玩家接下来所做的一系列操作。你的任务是，在各次操作之后及时计算出新的珠子序列。输入第一行是一个由大写字母'A'~'Z'组成的字符串，表示轨道上初始的珠子序列，不同的字母表示不同的颜色。第二行是一个数字n，表示整个回放过程共有n次操作。接下来的n行依次对应于各次操作。每次操作由一个数字k和一个大写字母Σ描述，以空格分隔。其中，Σ为新珠子的颜色。若插入前共有m颗珠子，则k∈[0,m]表示新珠子嵌入之后（尚未发生消除之前）在轨道上的位序。输出输出共n行，依次给出各次操作（及可能随即发生的消除现象）之后轨道上的珠子序列。如果轨道上已没有珠子，则以“-”表示。样例见英文题面限制0≤n≤10^40≤初始珠子数量≤10^4时间：2sec内存：256MB灯塔(LightHouse)DescriptionAsshowninthefollowingfigure,Ifanotherlighthouseisingrayarea,theycanbeaconeachother.Forexample,infollowingfigure,(B,R)isapairoflighthousewhichcanbeaconeachother,while(B,G),(R,G)areNOT.Input1stline:N2nd~(N+1)thline:eachlineisXY,meansalighthouseisonthepoint(X,Y).OutputHowmanypairsoflighthoursescanbeaconeachother(Foreverylighthouses,Xcoordinateswon'tbethesame,Ycoordinateswon'tbethesame)ExampleInput3224351Output1RestrictionsFor90%testcases:1=n=3*105For95%testcases:1=n=106Foralltestcases:1=n=4*106Foreverylighthouses,Xcoordinateswon'tbethesame,Ycoordinateswon'tbethesame.1=x,y=10^8Time:2secMemory:256MBHintsTherangeofintisusually[-231,231-1],itmaybetoosmall.描述海上有许多灯塔，为过路船只照明。（图一）如图一所示，每个灯塔都配有一盏探照灯，照亮其东北、西南两个对顶的直角区域。探照灯的功率之大，足以覆盖任何距离。灯塔本身是如此之小，可以假定它们不会彼此遮挡。（图二）若灯塔A、B均在对方的照亮范围内，则称它们能够照亮彼此。比如在图二的实例中，蓝、红灯塔可照亮彼此，蓝、绿灯塔则不是，红、绿灯塔也不是。现在，对于任何一组给定的灯塔，请计算出其中有多少对灯塔能够照亮彼此。输入共n+1行。第1行为1个整数n，表示灯塔的总数。第2到n+1行每行包含2个整数x,y，分别表示各灯塔的横、纵坐标。输出1个整数，表示可照亮彼此的灯塔对的数量。样例见英文题面限制对于90%的测例：1≤n≤3×105对于95%的测例：1≤n≤106全部测例：1≤n≤4×106灯塔的坐标x,y是整数，且不同灯塔的x,y坐标均互异1≤x,y≤10^8时间：2sec内存：256MB提示注意机器中整型变量的范围，C/C++中的int类型通常被编译成32位整数，其范围为[-231,231-1]，不一定足够容纳本题的输出。#includestdio.h#defineL1000005inty[L],le[L],ri[L];longans=0;voidqsort(inta[],intb[],intl,intr){inti,j,x,t;i=l;j=r;x=a[i+((j-i)1)];do{while(xa[i])i++;while(xa[j])j--;if(i=j){t=a[i];a[i]=a[j];a[j]=t;t=b[i];b[i]=b[j];b[j]=t;i++;j--;}}while(i=j);if(ir)qsort(a,b,i,r);if(jl)qsort(a,b,l,j);}voidMerge(intl,intmi,intr){inti,j,k,n1=mi-l+1,n2=r-mi;constintMAX=100000005;for(i=1;i=n1;i++)le[i]=y[l+i-1];for(i=1;i=n2;i++)ri[i]=y[mi+i];le[n1+1]=MAX;ri[n2+1]=MAX;i=1;j=1;for(k=l;k=r;k++){if(le[i]ri[j])y[k]=ri[j++];else{y[k]=le[i++];ans+=long(n2)-j+1;}}}voidMerge_Sort(intl,intr){intmi;if(l==r)return;mi=l+((r-l)1);Merge_Sort(l,mi);Merge_Sort(mi+1,r);Merge(l,mi,r);}intmain(void){intn,x[L];scanf(%d,&n);for(inti=1;i=n;i++){scanf(%d%d\n,&x[i],&y[i]);}qsort(x,y,1,n);Merge_Sort(1,n);printf(%ld\n,ans);return0;}