http://codeforces.com/contest/1064/problem/D
这个题最操蛋的是我把复杂度弄错了导致没有敢写暴力。。不过官方并没有出题解所以我也不知道我的做法是否可行，只能说通过了目前的所有数据。
做的思路就是求出来原点到每个点所用的最小的left和最小的right，求的方法就是暴力bfs，但是这里有个问题是有可能会有一个点可以通过多条路径到达，那么该如何确定最小值？如果直接裸搜不打标记会使得无限循环，如果打标记则会使得多种可能没有考虑，我这里用了一个玄学剪枝就是当当前点的下一个点的数据有被更新的时候才加到queue里，否则就不加，可以保证去掉了很多无用的扩展也可以保证搜索可以结束。另外一个优化是加了点是否已经在queue内的判断，可以避免多余的入队操作（这个貌似也可以用在一般的dij里啊）
http://codeforces.com/contest/1064/problem/E
又是喜闻乐见的交互+二分，这个已经在cf的讨论区被吐槽两次了，每次出交互题都是二分。。。我一开始没有搞懂题意，以为是你随便给他出点它会自动调整让点可以分为两片区域，后来才意识到他是给定了点的颜色分布，就是第几个点你只要问就是安排好的，也就是说这个需要你掌握问的点的坐标。。。
但是在不知道下一个点是什么的时候如何发问呢，首先想简化的过程，如果问的点全在一条线上会发生什么：假设左边为白点右边为黑，那么那个分界线一定是先往一个方向走了几步，然后又得回头往另一个方向走，如此反复。那么如何保证每次“回头”都可以有足够的余地让继续走下去而不与之前定好的界限相交？想到了一个叫二分的东西。。在倍增法的实现里其实就可以发现，他每次都会减半所以每次都不会覆盖到原来的部分。
但是这个题目直接二分又是有问题的，因为最多可以有30个点，而[log2(1e9)]==29，也就是说有一种情况可能最后会有俩点重合，为了避免这种情况可以先ask一个(0,0)，并且以此确定左半边的颜色，而不是像一开始说的一样自己定左右颜色。这样的话就剩下了29个点需要处理了，1e9的范围可以保证无论如何二分都可以达到没有任何两个点重合的结果。这样的话只需要在分界处的两个点之间画一条斜线就可以了。
因为这个29的坑wa了n发。。。
继续阅读“[二分][精度][思维] codeforces1064E Dwarves, Hats and Extrasensory Abilities”
思路简单，就是求出来结果的所有质因数的指数+1乘起来就行了。
首先由于题目的要求这里读入的ai只有两种情况，要么ai=p*q是两个不相等素数的乘积，要么ai=p^k，其中k取2，3，4。显然后一种情况很容易处理，但是第一种就有些难受了，直接的想法是用一些优秀的O(N^(1/4))的非完美大整数分解算法（这个看tutorial的评论区神仙各有千秋）。但是由于第一类的数只能分解成两个质因数，而且我们最后要的是质因数的指数而不需要关心质因数本身是多少，所以就有了更好的策略：如果一个数字的质因数在其他数字中出现过，那么一定可以通过gcd求出来，这时候等于说另一个质因数直接一除也能求出来，等于这个ai就完全解决了，像第二种情况一样加到map里即可；如果说这个数的俩质因数都没有在其他数字中出现过那么我们肯定不能求出来这俩数字是多少了，但是我们可以知道出现了俩独特的质因数，他出现且仅出现在所有aj==ai里，那么我们可以把ai直接存进map里，存起来他对应的加了多少次，另外要单独开一个set记录下来哪些ai是这样的ai，最后计算的时候如果是这样的ai的话就乘以(1+map值)的平方就可以了。
所以说一定要分析所给数据的性质，他的约束是解题的难点但同时也可能是解题的突破口。
写的时候还有一点弄错了就是把哥德巴赫猜想和这个搞混了。。那个是+这个是*，而且哥德巴赫猜想在1e18的范围内一定是有一个小的和一个大的，这个小的不超过1e5好像，所以那个是只需要枚举小的然后判断大的是否为质数即可。
这个题wa到最后才意识到是dfs刷表的思想本身是错误的，必须按照拓扑序来处理，这两个是不等价的。不等价的原因是dfs可能会多次刷到同一节点而且这个节点的父节点还没有完全确定下来。比如当某个节点只有一个父节点的时候，本来dfs给了他1，也就是必胜态，但是如果某一次之后的刷新把父节点变成了1，那么由于该节点只有一个父节点所以他只能变成0。而原来写的dfs不能解决的就是这样一个问题：对于一个节点来说，是不是所有的父节点都是1或者至少有一个0，因为单纯的dfs可能会求很多遍这个点（如果不这样又没办法更新），如果用拓扑序的话就可以保证在搜到一个点的时候这个点的父节点已经全部搞定了，这也跟拓扑序处理的时候每次只走“一步”有关系。这样的话就可以保证不会有多余的1没有变成0了。
题意要求所有的T中的循环串在S中出现了多少次，多次出现重复计数。
先考虑处理循环串，我们可以把循环串往后复制一遍变成定长单串，这时候如果我们可以把处理定长单串的方法搞出来就也能搞出来循环了。现在考虑的是对于一个串T，以T[i]为结尾的长为n的串出现了几次。很容易想到用endpos的大小去求，所以应该先把endpos大小求出来，之后就是应该确定是哪个endpos。可以先考虑如何求出对于T[i]来说与S的最长公共子串，这时候只要在SAM上顺着fa树走一直到走到原点或者有可以往后转移就可以了。如果走到了根节点还是没有能转移的，那就说明就没有这个字符，直接全0就可以了。注意这时候的长度可能过大，也就是stl超过了n，而在计算的时候应该是只需要“刚刚好包含长度为n”的那个状态节点的endpos。所以需要再顺着fa往前跳到fa的len小于n就可以了。然后这时候还有一个重复计算的问题，这是由于循环串可能有重复产生的，这时候我们就得给同样的条件打上标记了，而怎么判断是同样的呢？显然当串相同的时候一定会走到相同的节点上，只需要在最后的+环节打标记就可以了。
wa点主要出在指针和状态下标的转换上以及数组的长度上，注意循环串要复制一遍的话得是2倍长度。。。emmm
https://cn.vjudge.net/problem/POJ-2763
欧拉序线段树裸题，每次要求出两点之间的距离，单点修改，区间查询。
欧拉序其实就是把树拍扁的一种方法。。。对给定的树先求出欧拉序，在欧拉序上通过权值的正负来抵消多余的往返操作，然后每次求得时候先求LCA，再求出lca到两个端点的距离相加即可。有了欧拉序LCA就是一个rmq问题，用线段树做就能实现动态求lca，然后端点距离可以用BIT或者仍然用线段树做，求和最后输出即为答案。
实现的主要注意点是下标之间的关系。。。。这其中欧拉序求出来的点个数是2*n-1，然后BIT上存储的又是2n-2个间隔，然后BIT差分又得考虑左端点往前移动一下。。
其实也不是正常意义上的meet in the middle了，只是这个处理的思想有点像。（似乎每次做交互题都会卡？
自己做的时候是理解错题目意思了，以为图上只要联通的点都能返回YES，但是其实是按照他的限制下走的时候能走到才能返回YES。这样的话需要考虑的问题就比较好处理了。。。。一开始理解的那种的话根本没法在4*n次询问的限制下做出来。
因为右下半矩阵的路线只能通过询问（1，1）到该点的可行性来获得，左上半矩阵的路线只能通过询问（n,n）到该点的可行性获得，要想获得完整的可行路线只能在交界重合的地方处理，也就是反对角线上的方块。为了使得两个方向的推法能够走到同样的对角线点上，可以采取极端策略，左边的就尽量往下走，右边的尽量往左走，这样两种操作到最后的结果都是相同的，会走到对角线上的极端点（最左下的可行点），这时候就保证了两条路能够接上。 继续阅读“[思维][meet in the middle] codeforces 1023 E”
http://codeforces.com/contest/1013/problem/D
题意：每次可以从矩形的3个角产生第4个角，问至少需要添加多少个方块可以使得让整张图都充满方块。
自己想的是奇怪的思路，因为发现一个联通的块可以扩展到这个块的maxx，maxy，但是之后就不知道怎么做了。看了题解才恍然大悟，原来是把坐标转化成二分图的左右节点，然后考虑连通分量的个数就可以了。证明的时候，首先注意到一点就是二分图中两个点之间的路径个数一定是奇数，对于同一个连通分量中的左右两个点x，y，他们之间的距离如果是1的话那说明二者之间一定有了一条路径了，也就是这个点已经有一个方块了，如果不是1那么至少是3，每次取距离y最近的3个点，按照题目中给的性质，就可以生成一条新的边，也就是从倒数第四个直接联到y，这样的话，每次边的数量都会-2，到最后一定能减少到1，回到之前的情况。所以在同一个连通分量里的左右所有的点一定能连到一起，也就是说所有的方块一定能被涂上。这时候等于说连通分量和能全部染色等价了，我们就只需要计算出来最少需要多少条边使整个图成为连通图就行了。。其实也就是 连通分量数-1
wa点的话因为把n+m写成了2*n错了还以为横纵坐标是一样大的。。。愚蠢的错误emmmm
这个题在codeforces上有几乎一模一样的：http://codeforces.com/contest/452/problem/F
cf上的题说的是考虑长度为3的等差序列，bzoj这个说的是等差序列其实也是找长度为3的，因为显然能找到长度大于3的肯定也能找到等于3的。cf那个题有个假算法可以过掉所有数据，就是暴力枚举中点，然后往左右延伸的时候不超过5个就行。。之所以能这么做是因为这个题目要想构造出来NO的数据确实很难。。不过假算法依然是假算法。。
正解是每次出现过一个点之后把他在线段树上值变为1，然后求一个中点左右两边有没有相同的时候需要判断左右两边是不是完全一样，如果不是一定有解。这里判断的方法是hash。。。分别在两个线段树上维护正反两个方向的左右01字符串的hash值就可以了。
wa点：首先是对于这种多项式形式的线段树合并的时候要分三种情况，完全在左/完全在右/跨越中点；其次是跨越中间点的情况下一定要考虑清楚应该累加的数值是多少。。在这里是pw[mid-max(ql,l)]；最后是当ai==1和ai==n时候的特判，这时候不能query，但是必须update，我一开始写了单独处理1，然后i从2开始循环，后来忽然意识到a1并不一定等于1啊。。。傻了。。。
http://codeforces.com/contest/1040/problem/E
这个做法最重要的是原本的每一条边两端点一定不相等，所以两个点如果同时被异或结果一定仍然不相等。 然后就是考虑一个点被异或另一个点没有被异或的情况，一开始觉得会很复杂？但是实际上不是这样的，远没有想象中的复杂： 当x确定的时候，只有a⊕b==x的那些边会受到影响，这些边必须同时被选中，而剩下的，无所谓。。所以就把这些边连起来的点缩点之后就成了2^q的选择方式了。。
实现细节：①会卡并查集退化，所以必须写按秩合并 ②每次只要记录下被改动的点，然后下一次把这些点并查集复原即可，否则由于并查集的初始化时间复杂度会退化。
