sb题

「SHOI2015」脑洞治疗仪

线段树维护最大子段和模板题

11操作求出[l0,r0][l_0, r_0]11的个数,然后在[l1,r1][l_1, r_1]上二分求出右端点,转化为区间置11

「SDOI2017」树点涂色

看到操作1很容易想到LCT,然后考虑路径的权值和LCT有什么关系

发现点xx到根路径的权值就是xx到根路径上经过的轻边个数+1,并且这个东西也有可减性

每条重链可以看成一个联通块,经过轻边就相当于跨过联通块,使权值+1

注意到,只有在access的时候会改变轻重边,那么用一棵dfn序线段树维护信息即可

例如,把当前xx的重儿子yy变成轻儿子,就相当于把yy所在splay中深度最浅的点的子树权值+1+1

「TJOI2015」旅游

Description

题面太屎,记录一下

给你一棵点权树(权值为valval)

每次询问两个点(x,y)(x, y),你要在xxyy的这条链上依次找出两个点a,ba, b,使得val[a]val[b]val[a] - val[b]最大

并且要支持点权链加

Solution

考虑序列上怎么做

直接线段树,维护min,maxmin, max,以及当前区间的答案(左右儿子答案与当前点的maxrsminlsmax_{rs} - min_{ls}取最大值)

在树上的话,套层树剖即可,注意不仅需要维护maxrsminlsmax_{rs} - min_{ls},还要维护maxlsminrsmax_{ls} - min{rs},因为树剖在跳的时后,一边是正的一边是反的

「LNOI2014」LCA

很经典的一个套路了,不过这道题一直没写

今天拿到这道题的时候居然还想了半天才想出来。。。

询问[l,r][l, r]显然可以拆成[1,l1][1, l-1][1,r][1, r],然后考虑离线求出前缀的答案

11nn的顺序,每次把ii到根路径上所有点权值+1

若询问xx,只要求xx到根路径权值和即可

「SDOI2010」捉迷藏

两个模板

最小值直接k-d tree

最大值转化成切比雪夫距离,直接求就行了