• 【bzoj1095】[ZJOI2007]Hide 捉迷藏

    【bzoj1095】[ZJOI2007]Hide 捉迷藏

    Description捉迷藏Jiajia和Wind是一对恩爱的夫妻,并且他们有很多孩子。某天,Jiajia、Wind和孩子们决定在家里玩捉迷藏游戏。他们的家很大且构造很奇特,由N个屋子和N-1条双向走廊组成,这N-1条走廊的分布使得任意两个屋子都互相可达。游戏是这样进行的,孩子们负责躲藏,Jiajia负责找,而Wind负责操纵这N个屋子的灯。在起初的时候,所有的灯都没有被打开。每一次,孩子们只会躲藏在没有开灯的房间中,但是为了增加刺激...

  • 【bzoj2957】楼房重建

    【bzoj2957】楼房重建

    Description  小A的楼房外有一大片施工工地,工地上有N栋待建的楼房。每天,这片工地上的房子拆了又建、建了又拆。他经常无聊地看着窗外发呆,数自己能够看到多少栋房子。为了简化问题,我们考虑这些事件发生在一个二维平面上。小A在平面上(0,0)点的位置,第i栋楼房可以用一条连接(i,0)和(i,Hi)的线段表示,其中Hi为第i栋楼房的高度。如果这栋楼房上任何一个高度大于0的点与(0,0)的连线没有与之前的线段相交,那么这栋楼房...

    12015年4月17日2,043线段树
  • 【bzoj2770】YY的Treap

    【bzoj2770】YY的Treap

    Description志向远大的YY小朋友在学完快速排序之后决定学习平衡树,左思右想再加上SY的教唆,YY决定学习Treap。友爱教教父SY如砍瓜切菜般教会了YY小朋友Treap(一种平衡树,通过对每个节点随机分配一个priority,同时保证这棵平衡树关于priority是一个小根堆以保证效率)。这时候不怎么友爱的510跑了出来,他问了YY小朋友一个极不和谐的问题:怎么求Treap中两个点之间的路径长度。YY秒了之后决定把这个问题交给你...

    02015年4月16日1,472STL,二分法,线段树
  • 【bzoj3638/3272】Cf172 k-Maximum Subsequence Sum

    【bzoj3638/3272】Cf172 k-Maximum Subsequence Sum

    Description给一列数,要求支持操作:1.修改某个数的值2.读入l,r,k,询问在[l,r]内选不相交的不超过k个子段,最大的和是多少。InputThefirstlinecontainsintegern(1 ≤ n ≤ 105),showinghowmanynumbersthesequencehas.Thenextlinecontainsnintegersa1, a2, ..., an(|ai| ≤ 500).Thethirdlinecontainsintegerm(1 ≤ m ≤ 105)—thenumberofqueries.Thenextmlinescontainthequeriesintheformat,giveninthestate...

    22015年4月16日1,539费用流,线段树
  • 【fjwc2015】当小威遇上经济危机

    【fjwc2015】当小威遇上经济危机

    格式问题比较大题面就不贴了tex搞的pdf太酷炫大意给定一棵树,支持修改点权,询问某个点子树内最大值是否超过根[crayon-58fd5bfdaef58327187521/] 

    52015年2月4日1,195dfs序,线段树
  • 【bzoj3813】奇数国

    【bzoj3813】奇数国

    Description在一片美丽的大陆上有100000个国家,记为1到100000。这里经济发达,有数不尽的账房,并且每个国家有一个银行。某大公司的领袖在这100000个银行开户时都存了3大洋,他惜财如命,因此会不时地派小弟GFS清点一些银行的存款或者让GFS改变某个银行的存款。该村子在财产上的求和运算等同于我们的乘法运算,也就是说领袖开户时的存款总和为3100000。这里发行的软妹面额是最小的60个素数(p1=2,p2=3,…,p60=281),任何人...

  • 【codechefTASTRMAT】String Matching

    【codechefTASTRMAT】String Matching

    其实我没有参赛。。。在比赛时间被人拉去做了这一道。。。你们就坑我吧设L=n-m对于B的第1个字符,其匹配的是A的一个区间1到1+L若其与A[1]不同,则hash值增加100001^m与A[1+K]不同,则hash值增加100001^(n-K)用数据结构支持查询1到1+L对hash值的贡献即第K位与B的第1个字符不同则hash值增加100001^(n-K),相同增加0用个线段树or树状数组(实际上前缀和就行)接着考虑对于B的第2个字符,其匹配的是A的一个区间2到2+L若...

    02014年12月28日908线段树,乘法逆元
  • 【cf498D】Traffic Jams in the Land

    【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日997线段树
  • 【poj3237】Tree

    【poj3237】Tree

    DescriptionYouaregivenatreewithNnodes.Thetree’snodesarenumbered1throughNanditsedgesarenumbered1throughN−1.Eachedgeisassociatedwithaweight.Thenyouaretoexecuteaseriesofinstructionsonthetree.Theinstructionscanbeoneofthefollowingforms:CHANGEivChangetheweightoftheithedgetovNEGATEabNegatetheweightofeveryedgeonthepathfromatobQUERYabFindthemaximumweightofedgesonthepathfromat...

    02014年12月21日1,619线段树,树链剖分
  • 【bzoj3747】[POI2015]Kinoman

    【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],...

    12014年12月19日1,763线段树
  • 【bzoj3306】树

    【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日2,366dfs序,线段树,树上倍增
  • 【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日1,866dfs序,线段树
  • 【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日1,588线段树