• 「BZOJ3653」谈笑风生

    「BZOJ3653」谈笑风生

    Description设T为一棵有根树,我们做如下的定义:•设a和b为T中的两个不同节点。如果a是b的祖先,那么称“a比b不知道高明到哪里去了”。•设a和b为T中的两个不同节点。如果a与b在树上的距离不超过某个给定常数x,那么称“a与b谈笑风生”。给定一棵n个节点的有根树T,节点的编号为1到n,根节点为1号节点。你需要回答q个询问,询问给定两个整数p和k,问有多少个有序三元组(a;b;c)满足:1.a、b和c为T中三个不同的点,且a为p号节...

    02014年12月8日2,971dfs序,线段树
  • 「BZOJ3226」[SDOI2008] 校门外的区间

    「BZOJ3226」[SDOI2008] 校门外的区间

    Description  受校门外的树这道经典问题的启发,A君根据基本的离散数学的知识,抽象出5种运算维护集合S(S初始为空)并最终输出S。现在,请你完成这道校门外的树之难度增强版——校门外的区间。  5种运算如下:UTS∪TITS∩TDTS-TCTT-SSTS⊕T  基本集合运算如下:A∪B{x:xÎAorxÎB}A∩B{x:xÎAandxÎB}A-B{x:xÎAandxÏB}A⊕B(A-B)∪(B-A)Input  输入共M行。  每行的格...

    02014年11月25日2,142线段树
  • 「NOIP模拟赛」密码

    「NOIP模拟赛」密码

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

    22014年11月2日1,880贪心,线段树,二分法
  • 「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日1,272线段树
  • 「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日1,353线段树
  • 「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日8,479树套树,线段树
  • 「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,768ST表,二分法,线段树
  • 「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日5,562线段树
  • 「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日3,323线段树,离线处理
  • 「BZOJ2212」[POI2011] Tree Rotations

    「BZOJ2212」[POI2011] Tree Rotations

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

    02014年8月25日2,540线段树
  • 「ch52」还教室

    「ch52」还教室

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

    12014年8月18日2,059线段树
  • 「NOIP模拟赛by wulala」公主的朋友

    「NOIP模拟赛by wulala」公主的朋友

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

    02014年8月16日1,217线段树