百题试炼（复活版）

题目	思路	代码
[SCOI2005] 王室联邦[SCOI2005] 王室联邦	树上分块板题，考虑一个栈，dfs时如果一个子树栈的大小已经可以单开一个块了，就新开一个块，让其根为x，如果有暂时无法解决的，就先塞进去，别人pop时拉一条“警戒线”，不允许他pop。到最后点数量不够B，不能单开一块，就将其进入到最后一个块中。	代码
SP10707 COT2 - Count on a tree II SP10707 COT2 - Count on a tree II	用括号序将树上操作改为线性操作，易得出结论：两点之间的路径为其在线性序列上的中间元素，特别的，对于中间出现两次的元素不能算贡献因为他相当于进来又出来了，不在路径内，尤其特别的，若LCA不在序列中，需将LCA加进去	代码
苹果树苹果树	与上题代码相似，加特判色盲即可	代码
Ex - Yet Another Path Counting (AI)Ex - Yet Another Path Counting (AI)	一眼采花生，世界就是一个大大的采花生(雾)，但是采花生只针对一部分数据，所以我们对另一部分数据的路径数采用组合数学计算，这玩意路径选择相当A(i,j)，B(x,y),在（x-i+y-j）个选择中选（x-i）个向右走，或者向下移是同理，这是典型的根号分治	代码
#loj144. DFS 序 1#loj144. DFS 序 1	用dfs序转成序列操作，树状数组维护之	代码
#jzyz3182. 【高手训练】字符串排序 jzyz3182. 【高手训练】字符串排序	显然是个线段树啊，只不过LazyTag变为了是否为升降序，代码实现很简单但是码量大	代码
#jzyz530. [CF1477B]Nezzar and Binary String #jzyz530. [CF1477B]Nezzar and Binary String	首先题意有些难懂，总之就是要优先满足她的要求，其次在判断能否达到目标。发现如果我们按题目说的顺序做的话比较难做，所以正难则反，考虑倒着做，对答案是没影响的	代码
#abc223fL. F - Parenthesis Checking (AI) #abc223fL. F - Parenthesis Checking (AI)	这道题对我来说挺不错的，那就是让我认识到了一个处理合法括号序的常用操作，当且仅当 $cnt_(==cnt_)$ (这么个玩意相当于其区间和为0)且将(视作+1,)视作-1，对于任意的一个i都有其前缀和大于等于0。知道这个结论后，做法很显然啊，使用线段树维护区间前缀和和最小值及区间和，当区间和恰好为0且最小前缀和大于等于0时答案为真	代码
#abc256hL. Ex - I like Query Problem (AI)吗？	讲这题前我要先讲一下花神 (挖坑)
#BZOJ3211. 花神游历各国 #BZOJ3211. 花神游历各国	首先我们都知道开根号且向下取整值下降会很快，即使是1e5 也承受不了几下就会变成1，以后的操作对于这个区间来说已经没有意义了，所以考虑将lazytag改为是否整个区间均为1，是则不用修改，经过势能分析后发现时间复杂度优秀，然后就做完了。	代码
#abc256hL. Ex - I like Query Problem (AI)#abc256hL. Ex - I like Query Problem (AI)	显然与花神那题有异曲同工之妙，只是多了个操作罢了	代码
abc331fL. F - Palindrome Query (AI)abc331fL. F - Palindrome Query (AI)	回文串是吧，如何高效判断呢，可以将回文串撕成两半，计算它们的Hash值，判断即可	代码
#P946G. Almost Increasing Array #P946G. Almost Increasing Array	DP，然后线段树优化之，是因为这是线段树作业，可是我觉得这活我们树状数组也能做啊	代码
#P1705E. Mark and Professor Koro#P1705E. Mark and Professor Koro	很巧妙地一道题，需要将合并的操作转化成二进制高精度加法，然后就分类讨论，将修改看作删除后在加，使用线段树维护即可(这个唐人手敲线段树的时候change的时候没有pushup导致俩人瞪了30min没查出来QAQ)	代码
矩阵乘法矩阵乘法	二维整体二分！！！我对整体二分的理解已经深入骨髓了！！！总之就是将整体二分中的树状数组改成二维的，然后在ask外面套一个前缀和即可	代码
天天爱射击天天爱射击	小水题，考虑不是对每个子弹打木板，而是木板被子弹打，整体二分即可，注意树状数组的add时，add是下标，所以上限应是2e5，不能是n，否则你就会样例不过但是可以AC(这不好事么？)	代码
【模板】字典树【模板】字典树	建个Trie跑就行了	代码
The XOR Largest PairThe XOR Largest Pair	利用异或的性质，不同为1，相同为0，所以每个数都二进制拆分，尽可能地反向跑就可以做到最大	代码
Compress Words Compress Words	hash水过。。。。。	代码
Distinct SubstringsDistinct Substrings	结论题:字符串中本质不同的字串数量为 $(n+1)*n/2-\sum_{i=2}^{i<=len}height[i]$ 证明也是不难的，就是总子串的数量减去重复的吗，重复的数量，不就是相邻两个的后缀的最长前缀之和吗	代码
串分割串分割	看到最大值最小，考虑到了二分答案，破环之后，二分起始位置就做完了	串分割
「AHOI2013」差异「AHOI2013」差异	式子题先拆式子 $\frac{n(n+1)(n-1)}{2}-2*\sum _{i=1}^{i<=n}\sum _{j=1}^{j<=n}lcp(i,j)$ 前半部分好说，后半部分使用lcp的一个性质， $lcp(i,j)=min(lcp(i,k),lcp(k,j)),i<=k<=j$ ，由此我们可以推广知，lcp(i,j)就等于i到j区间任意两个相邻的height，取min。最后在加起来，而区间最值和使用单调栈维护	代码
「NOI2015」品酒大会「NOI2015」品酒大会	好题！用了一个转换的思想，因为r相似和我们的height数组非常之像，所以我们考虑对枚举到的每个r，看作分割(毕竟我们选酒时必须是连续的height>r的，中间不能经过任何一个height<r)，对每个连通块单独算贡献。另外对于答案算乘积最大值，发现他给的数据有负数，所以最大值只可能是两最大值相乘或最小值相乘(两个绝对值很大的负数吗)，结果发现如果按分割的思路的话，区间最大最小值是不好维护的，所以我们考虑，倒着做由分割变成合并操作，使用并查集维护即可。总之是一道思路层层递进的绝世好题。	代码
「SDOI2016」生成魔咒「SDOI2016」生成魔咒	如果按正常思路去做的话，每新加进一个字符所有之前算好的height全都没有用了，所以考虑将在末尾插，变成插到开头，很有道理，然后就做完了	代码
工艺工艺	最小表示法版题	代码
NecklaceNecklace	第二问是版题，第一问有个小结论，那就是最小表示法一样的两个字符串一定是某个字符串的循环同构，这挺显然的吧	代码
隐藏口令隐藏口令	最小表示法都这么版吗？？？？	代码
最长双回文串最长双回文串	Manacher，枚举中间那个连接点就做完了	代码
Prefix-Suffix Palindrome (Hard version)	有意思的题，卡了我好久。首先应该不难发现，答案应该是由原串最长前后缀加上去掉最长前后缀后的贴着边界的最长回文子串相加，挺有意思的反正。	代码
TJOI2015」弦论TJOI2015」弦论	首先t=0是好处理的，t=1就是先DP一遍在跑t=0	代码

没错，在经过了很久以后，100好题分享又复活了。。。。并正式更名为百题试炼！！！！

BZOJ2733. 永无乡

就是维护一个主席树合并+并查集的事

F - Distance Component Size Query

因为一个连通块必然是一段连续的区间，并且这个区间在内部查询时的间隔都小于K，并且答案具有单调性，所以我们左边右边各二分一次，内部使用线段树维护区块内的联通块数量，就能拿到答案区间的两个端点，ans=rans-lans+1。

[FJOI2015]火星商店问题

神秘的可持久化Trie树，跟主席树很像，也是记录历史版本，开了好几个rt，但是还多记了一个size，每次区间询问异或最大值时就那r的siz-l的siz，如果siz>0 说明l~r里面有点满足这个。

多说无益，看看代码

void insert(int &y,int x,int v){
	y=++idx; int p=y;
	for(int j=17;j>=0;j--){
		bool now=v&(1<<j);
		ch[p][now^1]=ch[x][now^1];
		ch[p][now]=++idx;
		p=ch[p][now];
		x=ch[x][now];
		siz[p]=siz[x]+1;
	}
}
ll ask(int l,int r,int v){
	ll res=0;
	for(int j=17;j>=0;j--){
		bool now=v&(1<<j);
		if(siz[ch[r][now^1]]-siz[ch[l][now^1]]>0){ r=ch[r][now^1];l=ch[l][now^1];res|=(1<<j); }
		else{ r=ch[r][now];l=ch[l][now]; }
	}
	return res;
}

还挺好懂的不是吗，这篇总结又要咕咕咕咕咕了。

然后这道题相当于有两个维度我们对着时间进行线段树合并，拿可持久化Trie搞店铺这一维。