rt，原因如下：

首先是极其麻烦恶心的预处理（用stl另当别论，但也挺麻烦的）

其次是考虑到倍增优化dp，并设计出状态，然后借助预处理得出答案

最后是亿点点要考虑的细节，对于像我这样刚学倍增优化的蒟蒻真的很难了qwq

以上只是个人观点，假如只是因为蒟蒻太菜不会做，还请大佬轻喷