解 1
我们发现只需要关心处于结果字符串前 \(k\) 位的字符。
因此考虑从后往前处理。
对于一个询问区间，我们暴力连边，用并查集维护， \(x\) 的父亲等于 \(y\) 相当于位于 \(x\) 的字符是从位于 \(y\) 的字符处复制过来的，然后删掉这个区间，更新其他元素的排名，用线段树维护。复杂度 \(O(k\log k)\) ，刚好可以通过本题。
解 2
syk：用平衡树维护暴力
复杂度是对的，而且更优： \(O(n\log n+k)\) 。
\(O(\text{可以通过}15\%\text{的数据})\)
然后你发现，第14个点的答案一定是0。
所以加起来你就有20分了。
易得计算 \(f(a,b)\) 的复杂度是 \(\log\) 的。
所以 \(x,y\le 1000\) 的数据是送你的。
然后在打 \(x=1,2,4,y\le 10^{18}\) 的时候，你发现好像是有一些规律的，这使得你能把 \(x\le 1000,y\le 10^{18}\) 的数据都过掉。
剩下的只有\(\text{Q}\color{red}{\text{iyang}}\)会
转载于:https://www.cnblogs.com/BlogOfchc1234567890/p/11622887.html
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
