牛客练习赛39

走方格

找规律。
首先考虑斜着走，每走一步都会使横坐标和纵坐标的距离减1，可以持续这个操作使得两个点处在同一水平或者竖直的线上。此时每斜着走两步会使距离减2。所以如果它们的距离为偶数，那么可以按照两步两步的走过去，否则先到达终点旁边的格子，再花费一次上下左右走的次数，到达终点。
复杂度O(1)
标程

选点

dfs序+LIS。
因为根节点的权值最小，其次是右子树的点，最后是左子树的点，所以按照先根，再右子树，再左子树的顺序dfs整棵树，求出dfs序，在dfs序上求最长上升子序列。
复杂度O(nlogn)
标程

流星雨

概率dp。
设 为第i天下雨的真正概率，由于第i天的概率只与第i-1天有关，所以有

复杂度：加上求逆元的复杂度，O(nlogn)
标程

动态连通块

并查集+bitset优化。
操作二可以在加边的过程中求出。即加入一条端点同色的边，并查集判断是否可以消去一个白（黑）连通块。
操作三求的是x,y所在的两个白连通块都连出的黑点（假设x,y是白色，黑色的情况是一样的）。
于是可以bitset维护每个白联通块连出的黑点，黑连通块连出的白点。每加入一条端点异色的边，在两个白、黑连通块的bitset中将一个位置设为1；加入一条端点同色的边，就是合并白（黑）连通块的过程，同时合并两个白（黑）连通块的bitset。
复杂度 ，W=32或64
标程

车站

线段树+倍增+LCA。
首先车站一定在所有铁路的经过的点的交集上，所以可以用线段树求出区间路径的交集，同时维护离路径交的两个端点最远的点。找到出了最远的两个点后，那么可以倍增求出车站的位置。
具体地，线段树每个节点维护u,v,du,dv，u,v是路径交，du,dv是分别是距离u,v最远的点。合并两个区间的过程是先对两个区间的路径求路径交，然后新的du,dv一定是两个区间中四个du,dv中的两个。
对一段区间询问，先求出区间的u,v,du,dv，于是可以选择路径du->dv上中间的位置作为车站，如果中间点不在路径交集上，那么让u,v中的一个作为车站。
复杂度O(nlogn)
标程

异或树

按位处理+线段树合并。
首先按位处理，那么问题转化为求一个子树内，权值大于x的，1（或0）的个数。
可以对每棵子树建立一棵权值线段树，每个叶子节点维护两个值size和cnt[]，表示这个权值出现的次数，以及这个权值二进制分解后，每一位上1的个数。权值线段树每个节点维护cnt[]，表示子树内二进制下每一位上1的个数和，现在可以在 处理每个关于子树u的询问了，V是值域。
然后dfs过程中，线段树合并来维护每个节点的权值线段树，线段树合并的过程中是合并到叶子节点的，合并的过程同时记录每个叶子节点出现的次数，出现偶数次就是代表这个权值消失了。
标程