• 【NOIP模拟赛】密码

    【NOIP模拟赛】密码

    【问题描述】哪里有压迫,哪里就有反抗。moreD的宠物在法庭的帮助下终于反抗了。作为一只聪明的宠物,他打算把魔法使moreD的魔法书盗去,夺取moreD的魔法能力。但moreD怎么会让自己的魔法书轻易地被盗取?moreD在魔法书上设置了一个密码锁,密码锁上有一个问题。施以斯卧铺魔法吧,你有M次机会,如此将得完美密码。然后是一串小写字母串。moreD的宠物斯卧铺魔法就是施法时的字符串其中相邻两位交换。而moreD对于完美密码的...

    22014年11月2日1,368贪心,线段树,二分法
  • 【codecomb2098】stone

    【codecomb2098】stone

    Descriptionn个石堆围成一圈,提供两种操作:1、每次将[L,R]堆的石子数量+k,其中,1<=L,R<=n,k>=0。2、询问有最多石子的那一堆有多少石子。现在,要求在线解决该问题。Input第一行两个整数n和m,n表示石子圈的长度,m表示操作数量。以下m行,首先一个是整数t,t=1或2,表示是哪种操作。 如果t=1,则后面跟三个整数l,r,k,表示区间[l,r]的所有石子堆石子数量+k,如果t=2表示上述询问操作。 Output 对于...

    02014年10月16日978线段树
  • 【codecomb2096】lyz

    【codecomb2096】lyz

    Description滑冰俱乐部初始有1->n号码溜冰鞋各k双,已知x号脚的人可以穿x->x+d号码的鞋子。现在有m次操作,每次两个数r、x,表示r号脚的人来了x个,x为负表示离开。对于每次操作,输出溜冰鞋是否足够。Input第一行四个整数n,m,k,d。以下m行,每行一个操作。Output对于每一个询问,输出是否可行。若可行,输出TAK,反之,输出NIE。Sample Input4 4 2 11 32 33 32 -1Sample OutputTAKTAKNIETA...

    02014年10月16日963线段树
  • 【bzoj3110】[Zjoi2013]K大数查询

    【bzoj3110】[Zjoi2013]K大数查询

    Description有N个位置,M个操作。操作有两种,每次操作如果是1abc的形式表示在第a个位置到第b个位置,每个位置加入一个数c如果是2abc形式,表示询问从第a个位置到第b个位置,第C大的数是多少。Input第一行N,M接下来M行,每行形如1abc或2abcOutput输出每个询问的结果SampleInput2511211122211221112123SampleOutput121HINTN,M<=50000,N,M<=50000a<=b<=N1操作中abs(c)<=N2操作中abs(c)<=M...

    272014年10月8日5,470树套树,线段树
  • 【cf475D】CGCDSSQ

    【cf475D】CGCDSSQ

    Givenasequenceofintegersa1, ..., anandqqueriesx1, ..., xqonit.Foreachqueryxiyouhavetocountthenumberofpairs(l, r)suchthat1 ≤ l ≤ r ≤ nandgcd(al, al + 1, ..., ar) = xi.isagreatestcommondivisorofv1, v2, ..., vn,thatisequaltoalargestpositiveintegerthatdividesallvi.InputThefirstlineoftheinputcontainsintegern,(1 ≤ n ≤ 105),denotingthelengthofthesequence.Thenextlinecont...

    02014年10月6日1,308ST表,二分法,线段树
  • 【bzoj3685】普通van Emde Boas树

    【bzoj3685】普通van Emde Boas树

    Description设计数据结构支持:1x 若x不存在,插入x2x 若x存在,删除x3   输出当前最小值,若不存在输出-14   输出当前最大值,若不存在输出-15x 输出x的前驱,若不存在输出-16x 输出x的后继,若不存在输出-17x 若x存在,输出1,否则输出-1Input第一行给出n,m表示出现数的范围和操作个数接下来m行给出操作n<=10^6,m<=2*10^6,0<=x<nSampleInput101111121371742132345362SampleOutput1-1222-1题解线段树写的又慢...

    52014年9月8日2,696线段树
  • 【bzoj3545】[ONTAK2010]Peaks

    【bzoj3545】[ONTAK2010]Peaks

    Description在Bytemountains有N座山峰,每座山峰有他的高度h_i。有些山峰之间有双向道路相连,共M条路径,每条路径有一个困难值,这个值越大表示越难走,现在有Q组询问,每组询问询问从点v开始只经过困难值小于等于x的路径所能到达的山峰中第k高的山峰,如果无解输出-1。Input第一行三个数N,M,Q。第二行N个数,第i个数为h_i接下来M行,每行3个数abc,表示从a到b有一条困难值为c的双向路径。接下来Q行,每行三个数vxk...

    22014年8月26日2,259线段树,离线处理
  • 【bzoj2212】[Poi2011]Tree Rotations

    【bzoj2212】[Poi2011]Tree Rotations

    DescriptionByteasarthegardenerisgrowingararetreecalledRotatusInformatikus.Ithassomeinterestingfeatures:Thetreeconsistsofstraightbranches,bifurcationsandleaves.Thetrunkstemmingfromthegroundisalsoabranch.Eachbranchendswitheitherabifurcationoraleafonitstopend.Exactlytwobranchesforkoutfromabifurcationattheendofabranch-theleftbranchandtherightbranch.Eachleafofthetreeislabelledwithanintegerfro...

    02014年8月25日1,733线段树
  • 【ch52】还教室

    【ch52】还教室

    还教室还记得NOIP2012提高组Day2中的借教室吗?时光飞逝,光阴荏苒,两年过去了,曾经借教室的同学们纷纷归还自己当初租借的教室。请你来解决类似于借教室的另一个问题。【问题描述】在接受借教室请求的n天中,第i天剩余的教室为ai个。作为大学借教室服务的负责人,你需要完成如下三种操作共m次:1第l天到第r天,每天被归还d个教室。2询问第l天到第r天教室个数的平均数。3询问第l天到第r天教室个数的方差。【输入格式】第一行包括两个...

    12014年8月18日1,461线段树
  • 【NOIP模拟赛by wulala】公主的朋友

    【NOIP模拟赛by wulala】公主的朋友

    出题人说:正解分块。。。但是这不是和某次cf的dzylovescolor一样么TT修改的时候顺便查询,如果要修改的这一段宗教相同,打个标记并且统计答案后return否则递归复杂度我们可以这样想因为如果修改1-n,但是宗教都不同,这样是每个都要递归到最下面,这样一次修改就要nlogn但是这种情况并不会一直出现,询问完后1-n会被修改成同一种宗教,再把1-n变成不同的,又要额外修改n次也就是说,每次修改,最多让后面的查询多一个logn所以这样...

    02014年8月16日900线段树
  • 【bzoj1576】[Usaco2009 Jan]安全路经Travel

    【bzoj1576】[Usaco2009 Jan]安全路经Travel

    DescriptionInput*第一行:两个空格分开的数,N和M*第2..M+1行:三个空格分开的数a_i,b_i,和t_iOutput*第1..N-1行:第i行包含一个数:从牛棚_1到牛棚_i+1并且避免从牛棚1到牛棚i+1最短路经上最后一条牛路的最少的时间.如果这样的路经不存在,输出-1.SampleInput45122132344321243输入解释:跟题中例子相同SampleOutput336输出解释:跟题中例子相同题解首先用dijkstra得出最短路径树然后我的做法是树链剖分+线段树对于一条不在最...

    12014年8月7日2,656线段树,树链剖分
  • 【bzoj2304】[APIO2011]寻路path

    【bzoj2304】[APIO2011]寻路path

    DescriptionTooDee是一块二维格子状的土地(就像著名的笛卡尔坐标系那样),在这里生活着很多可爱的Dee。Dee是像蜜蜂一样的小动物,它们只在二维活动,而且它们非常的文明开化。TooDee的蜂窝和正常世界的蜂窝也是很不一样的,它们是矩形的且它们的边平行于TooDee的地理坐标系,就是说矩形的边或者是东西走向,或者是南北走向。因为Dees是很高级的生物,它们有很多固定的飞行轨道,这些轨道由一些平行于坐标轴的线段组成,...

    02014年8月5日2,614模拟,spfa,dijkstra,线段树
  • 【poj3321】Apple Tree

    【poj3321】Apple Tree

    DescriptionThereisanappletreeoutsideofkaka'shouse.Everyautumn,alotofappleswillgrowinthetree.Kakalikesappleverymuch,sohehasbeencarefullynurturingthebigappletree.ThetreehasNforkswhichareconnectedbybranches.Kakanumberstheforksby1toNandtherootisalwaysnumberedby1.Appleswillgrowontheforksandtwoapplewon'tgrowonthesamefork.kakawantstoknowhowmanyapplesarethereinasub-tree,forhisstudyoftheproduceabi...

    02014年8月1日683dfs序,线段树