本文共 825 字，大约阅读时间需要 2 分钟。
我之前一直担心极限数据的大小，5000(n,m)*100000(k)，用二维数组存储的话，空间基本上勉强可以撑住，但时间上可能就不够用了。所以我开始思考能不能用更高效的存储方式。
于是，我决定用两个一位数组分别表示行和列。这样，每次修改操作的时间复杂度就降到了O(1)。而查询操作虽然看起来复杂度是O(nm)，但实际上只需要查询一次，因为数据结构的特性决定了只需要一次查询就可以得到结果。
总体来说，这种方法的时间复杂度是O(nmk)，虽然看起来有点高，但因为每次查询只需要一次，所以实际运行效率还是可以接受的。
一开始，我想的方向有点偏差，后来我意识到应该从结果倒推。也就是说，从“a”这个结果出发，逆推可能的答案序列。这在小样例中是可行的，但当数据量变大时，方法就不太奏效了。
于是，我开始另辟蹊径。观察到数据范围很小，我决定直接枚举所有可能的答案序列。对于每一个序列，我会检查它是否可以通过某种脱水缩合的过程变成“a”。如果可以，那么这个序列就是合法的答案；否则，就不是。
这种方法的时间复杂度大约是6的排列，也就是30-50万级别的样子。加上检验的操作，总体复杂度还是在O(100W)以内，这样的效率对于当前的数据量来说是可以接受的。
一开始，我也考虑过使用线段树来解决这个问题。但在具体实现的时候，我不知道该怎么维护数据结构。后来，我决定放弃线段树，改用暴力方法来解决。
对于一个给定的式子，比如f2[f[1]]=k2(k1+b1)+b2=(k1k2)+(k2b1+b2)，我发现它非常适合用线段树来处理。叶子节点直接存储ki和bi，这是很直观的。然后，每个内部节点的k和b都可以通过其子节点的k和b计算得到。最后，我只需要套用标准的线段树模板，并不需要懒惰标记，就可以实现了。
这种方法的时间复杂度是O(nlogn + mlogn)，在数据量不大的情况下，效率非常高。
转载地址：http://yjgfk.baihongyu.com/