[数据结构]

sb题

「SHOI2015」脑洞治疗仪

[线段树]

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

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

「SDOI2017」树点涂色

[LCT]

看到操作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]

两个模板

最小值直接k-d tree

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

「JXOI2017」颜色

[扫描线] [线段树]

枚举剩下的那一段区间

对于每种颜色ii处理出L[i],R[i]L[i], R[i]分别表示该颜色出现的最靠左,最靠右的位置

若一个区间[l,r][l, r]合法,则maxi=lr{R[Ai]}r\displaystyle \max_{i=l}^{r}\{R[A_i]\} \le r,且mini=lr{L[Ai]}l\displaystyle \min_{i=l}^{r}\{L[A_i]\} \ge l

显然,对于一个确定的右端点,左端点的范围是一段连续的区间;左端点确定时同理

就和这个题一模一样了

这里我看的题解的做法是,枚举右端点ii扫描线,maxi=lr{R[Ai]}r\displaystyle \max_{i=l}^{r}\{R[A_i]\} \le r这个限制直接二分找到最靠左的左端点;mini=lr{L[Ai]}l\displaystyle \min_{i=l}^{r}\{L[A_i]\} \ge l这个限制在扫描线的过程中搞个线段树,区间置00


20-5-16 UPD

看到了一个很sb的做法,把每个数字随机赋权,每种颜色最后一个出现的位置的权值等于之前该颜色所有权值的异或和

若区间异或和为0,则方案合法。用map简单统计即可

「BZOJ3439」 Kpm的MC密码

[trie] [可持久化]

倒着建可持久化trie,模板题

不知道为什么bzoj上一直会t,交到dark bzoj上能过