a memo
题意：排成一行的旅馆房间
checkin时找到最靠左的空闲的长度>=d的连续区间，输出区间的左端点\(r\)并入住
checkout时把从x开始的长度为d的区间变为空闲
线段树的区间合并问题？
空闲0\1表示，区间置0\1可以用打标记来实现。
如何找到满足条件的区间端点\(r\)呢？线段树每个结点维护的信息为从区间左端点开始的全0序列的长度ls，从区间右端点开始的全0序列的长度rs，区间中最长的全0序列长度ms。如果线段树某个结点ms>=d，那么最长的区间可以来入住，最长区间有三种情况：完全在左儿子的区间，横跨左右儿子的区间，完全在右儿子的区间。因为\(r\)要满足最靠左，所以依次尝试上面三种可能情况。
每张海报的坐标范围\(0<=l_i<=r_i<=10^7\)，线段树维护\(10^7\)长度的序列会爆内存。但是海报的数量\(1 <= n <= 10000\)，也就是线段树需要更新的区间端点数<=20000个，因此对坐标进行离散化处理。
这篇博客中指出普通的离散化在这个题中有些问题，考虑下面这组数据
1
2
31 10
1 4
6 10
离散化坐标映射后，1->0，4->1，6->2，10->3，更新完后，区间[0,1],[2,3]被后面两张海报覆盖，可见的海报数为2。而第一张海报在原始区间[5,5]仍然可见，答案应为3.
因此，如果排序后相邻两坐标\(x_i,x_{i+1}\)的差>1，则需要在两者之间插入一个数，使得离散后\(x_i,x_{i+1}\)的差也>1。区间\((x_i,x_{i+1})\)中可见的海报数为0或1，仅需要插入一个数，其信息在最终就能够被统计到。
题意：完成5种集合操作，输出最终的集合。
若把集合S用0\1序列来表示，则集合操作可转化为对连续子序列（区间）的操作。
\(T^C\)表示\(T\)的补集
| \(S \cup T\) | \(T\)区间置1 |
| \(S \cap T\) | \(T^C\)区间置0 |
| \(S - T\) | \(T\)区间置0 |
| \(T - S\) | \(S\)取反，\(T^C\)区间置0 |
| \(S \oplus T\) | \(T\)区间取反 |
区间操作有两种，置0\1和取反。置0\1可以用线段树打lazy tag来实现，取反也可以用打标记来实现。这里只用了一个标记，标记的种类有无标记、0、1、取反四种，打0\1标记时不需要考虑之前标记的类型，打取反标记时，若之前为0\1，则标记变为1\0，若之前为取反，则变为无标记，若之前为无标记，则变为取反标记。
最后，在完成所有操作后，下传所有标记。
题意：迷宫中的点从不同方向进入时有不同的转向，求起点到终点的最短路。
每个点除了坐标x，y外，还有方向属性d。用BFS求最短路，存储BFS树中结点的父结点用于路径还原。
学习了一种用strchr来得到字符id的写法。
最近学习了一下各种BBST，简单总结一下。
Splay Tree：区间操作强无敌…对[l,r)区间的操作，把l-1结点splay到树根，r结点splay到根的右结点，则根的右结点的左子树就是区间[l,r)，然后对这棵子树进行操作。一个splay操作的均摊复杂度为O(logn)。
常见操作：[l,r)区间每个数加a，每个结点维护一个加的数值的lazy_tag
[l,r)区间翻转，每个结点维护一个表示是否翻转的标记
在第k个元素后插入元素或区间，若是区间，则要先建成一棵bst，把第k个结点splay到树根，第k+1个结点splay到根的右孩子，把需要插入的子树接到右孩子的左孩子。
删除元素，得到区间[l,r)后摘除子树。
实现：刚开始看时还纳闷为什么在实现时都要先加根节点以及根节点的右孩子，然后把整个区间建在根的右孩子的左子树上。后来才想到对于整个区间[1,N+1)，这种做法相当于在开始和结尾各添加一个元素，对整个区间进行操作则需要把这两个结点splay到树根和根的右孩子，才能得到整个区间。在第一个元素前和最后一个元素后插入都需要借助这两个结点。
LCT用来维护有根树的森林。对任意结点v，Preferred Child（PC）的定义为：如果v没被访问过或者刚刚访问到v，则PC[v] = null；如果刚刚访问到v的孩子结点u所在的子树，则PC[v] = u。v到其preferred child（如果有）的边为preferred edge，preferred edge连接起来形成preferred path。需要表示的树（也就是直观上的树）称为represented tree。LCT把每一条preferred path维护成一个树，称为Auxiliary Tree，所用的数据结构为Splay Tree。
树链剖分是Heavy Light Decomposition，把一个结点的孩子分为重和轻，是按照树的结构来进行划分。LCT是Preferred Path Decomposition，是按照对结点的访问来划分的。
所有可能的数对数量为N×N
所求的（x，y）一定满足x，y互素，否则设公约数为t，（x，y）可由（x/t，y/t）得到
若（x，y）互素，那么（y，x）也互素
若能求出满足1<=x<=N，1<=y<=x的互素的（x，y），那么经过对称即可得到所有的数对（可从N×N的二维图上来理解）
求phi值时注意避免溢出
Welcome to Hexo! This is your very first post. Check documentation for more info. If you get any problems when using Hexo, you can find the answer in troubleshooting or you can ask me on GitHub.
1 | $ hexo new "My New Post" |