数据结构

[数据结构]

sb题

「SHOI2015」脑洞治疗仪

[线段树]

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

$1$操作求出$[l_0, r_0]$内$1$的个数，然后在$[l_1, r_1]$上二分求出右端点，转化为区间置$1$

「SDOI2017」树点涂色

[LCT]

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

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

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

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

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

「TJOI2015」旅游

Description

题面太屎，记录一下

给你一棵点权树(权值为$val$)

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

并且要支持点权链加

Solution

[线段树] [树链剖分]

考虑序列上怎么做

直接线段树，维护$min, max$，以及当前区间的答案（左右儿子答案与当前点的$max_{rs} - min_{ls}$取最大值）

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

「LNOI2014」LCA

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

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

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

按$1$到$n$的顺序，每次把$i$到根路径上所有点权值+1

若询问$x$，只要求$x$到根路径权值和即可

「SDOI2010」捉迷藏

[曼哈顿与切比雪夫距离]

[k-d tree]

两个模板

最小值直接k-d tree

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

「JXOI2017」颜色

[扫描线] [线段树]

枚举剩下的那一段区间

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

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

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

就和这个题一模一样了

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

「BZOJ3439」 Kpm的MC密码

[trie] [可持久化]

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

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