思路

并查集判环+树的直径。注意树有可能是不连通的。
树的直径通过两次bfs就能得到，具体证明见树的直径（最长路）的详细证明

思路

A操作由于是对全局节点增加一个值，显然暴力修改不可行，我们考虑使用一个temp保存A和S对数据的加减。由于有一个temp，所以I操作我们需要插入的val改为val-temp。对S，我们插入一个暂时的min-temp，然后删除左子树，然后删除之前插入的那个点。F命令使用FindByRank函数，略微修改下内部参数即可（因为原来是第k多）。本题要注意BZOJ该题使用cin，cout会RE。

思路

LIS变形，本来想O(n^2)暴力踩10^8结果TLE的悲伤故事，所以学习了一下O(nlogn)的LIS求法。
对于最朴素的做法我们使用dp在n^2时间可以求出一个数列的LIS，程序如下

1
2
3
4
5
6
7
8

int dp[MAXN],maxs=-1;
memset(dp,1,sizeof(dp));   //假装可以这么写
for(int i=0;i<n;i++){
    for(int j=0;j<i;j++){
        if(dp[i]>dp[j])dp[i]=max(dp[i],dp[j]+1);
    }
    maxs=max(dp[i],maxs);
}

1. !cnt||a[i]>q[cnt-1],那我们直接在数列尾部加上a[i]，得到的数列就是当前最大公共子序列
2. 不然我们能得到a[i]小于等于q数组最后一个元素。我们在这里对q进行二分查找，找到第一个大于等于a[i]的数然后将该位置的数替换为a[i]。

这样就能nlogn求出数列的LIS，我们维护1-i的递增子序列长度和i-n的递减子序列长度然后处理即可。

思路

考虑将区间异或转换，我们处理一个异或前缀和数组，我们能够发现通过前缀和数组原来i-j的区间异或变成了pre[j]^pre[i-1]。然后我们逐个插入前缀和pre[i]，再由高到低逐个枚举k的二进制位:

• 当k的第i位为1：显然我们要找一个使pre[i]异或后为1的数才能保证比k-1大。
• 当k的第i位为0：如果我们找到一个使pre[i]异或后为1的数，那么异或后的数肯定比k-1大，我们直接在ans中加上这种数的个数（所以节点上要维护一个val次数数组），然后异或为1的不再考虑，我们进入异或后该位为0的节点。

对每个前缀和的答案累加就是最后的答案。

思路

Treap模板题

关于A*

A*算法是一种启发式搜索的算法，通过设定合理的估价函数，我们能够减少不必要的搜索从而达到减低时间复杂度的目的。当我们计算A*算法时，我们维护一个优先队列，同时按照我们规定的估价函数来进行排序。我们这样定义一个估价函数：F=G+H。这里：
F：需要排序的估价函数值
G：从起点到当前点的花费
H：我们人为设定的估价函数值
在这里我们这样理解这个估价函数，我们从起点到终点，我们定义H为当前点到终点的距离，很显然根据G+H，绕路走的F是比较大的，F就是我们人为观感上的“绕路走”，A*的估价函数的意义就是少“绕路走”，同时我们常常使用的BFS就是没有估价函数的，所以即便一些步骤我们明明知道不会产生最优解，我们依然遍历了这些步骤，A*的估价函数则避免了这个问题。

思路

本题我们先用dijkstra计算t到每个点的距离，然后这个距离就是我们的估价函数，然后我们从s出发使用A*，然后等第k次出队列碰到t点我们输出距离。需要注意的是当s==t时k++，因为题目要求必须要走一条路。

参考

A*算法入门

思路

可持久化trie树和主席树的构造类似。这题与之前主席树不同的地方就是在树上建树，类似spoj cot那题。对第n个节点，我们维护根-n这条链上的字典树。然后求x-y路径上的异或最大值时我们用x上的字典树+y上的字典树-两倍lca的父亲的字典树（因为根到lca父亲的字典树加了两遍），然后就是对常规的01字典树的考察。

学习一下主席树的使用

终于蓝名。。

思路

构造线性方程cx+2^k*y=b-a，直接extgcd即可，注意对线性方程有通解计算公式:x1=x0+k*b/(gcd(a,b)),y1=y0-k*a/(gcd(a,b))。