线段树 - Page 3

「CF498D」Traffic Jams in the Land
Somecountryconsistsof(n + 1)cities,locatedalongastraighthighway.Let'snumberthecitieswithconsecutiveintegersfrom1ton + 1intheordertheyoccuralongthehighway.Thus,thecitiesareconnectedbynsegmentsofthehighway,thei-thsegmentconnectscitiesnumberiandi + 1.Everysegmentofthehighwayisassociatedwithapositiveintegerai > 1—theperiodoftrafficjamsappearanceonit.Inordertogetfromcityxtocityy(x <...
12014年12月25日4,620线段树

「POJ3237」Tree
DescriptionYouaregivenatreewithNnodes.Thetree’snodesarenumbered1throughNanditsedgesarenumbered1throughN−1.Eachedgeisassociatedwithaweight.Thenyouaretoexecuteaseriesofinstructionsonthetree.Theinstructionscanbeoneofthefollowingforms:CHANGEivChangetheweightoftheithedgetovNEGATEabNegatetheweightofeveryedgeonthepathfromatobQUERYabFindthemaximumweightofedgesonthepathfromat...
02014年12月21日6,013线段树,树链剖分
「BZOJ3747」[POI2015] Kinoman
Description共有m部电影，编号为1~m，第i部电影的好看值为w[i]。在n天之中（从1~n编号）每天会放映一部电影，第i天放映的是第f[i]部。你可以选择l,r(1<=l<=r<=n)，并观看第l,l+1,…,r天内所有的电影。如果同一部电影你观看多于一次，你会感到无聊，于是无法获得这部电影的好看值。所以你希望最大化观看且仅观看过一次的电影的好看值的总和。Input第一行两个整数n,m(1<=m<=n<=1000000)。第二行包含n个整数f[1],...
22014年12月19日5,077线段树
「BZOJ3306」树
Description给定一棵大小为n的有根点权树,支持以下操作:•换根•修改点权•查询子树最小值Input第一行两个整数n,Q,分别表示树的大小和操作数。接下来n行,每行两个整数f,v,第i+1行的两个数表示点i的父亲和点i的权。保证f<i。如果f=0,那么i为根。输入数据保证只有i=1时,f=0。接下来m行,为以下格式中的一种:•Vxy表示把点x的权改为y•Ex表示把有根树的根改为点x•Qx表示查询点x的子树最小值Output对于每个Q,输出子树最小值...
02014年12月11日7,479dfs序,线段树,树上倍增
「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日7,168dfs序,线段树
「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日4,267线段树
「NOIP模拟赛」密码
「问题描述」哪里有压迫，哪里就有反抗。moreD的宠物在法庭的帮助下终于反抗了。作为一只聪明的宠物，他打算把魔法使moreD的魔法书盗去，夺取moreD的魔法能力。但moreD怎么会让自己的魔法书轻易地被盗取？moreD在魔法书上设置了一个密码锁，密码锁上有一个问题。施以斯卧铺魔法吧，你有M次机会，如此将得完美密码。然后是一串小写字母串。moreD的宠物斯卧铺魔法就是施法时的字符串其中相邻两位交换。而moreD对于完美密码的...
22014年11月2日5,363贪心,线段树,二分法
「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日2,601线段树
「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日2,866线段树
「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日24,801树套树,线段树
「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日4,601ST表,二分法,线段树
「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日8,575线段树