首先第一篇题解在我这个机子上 $n=q=10^5$，操作全部为Q时跑了 $3\rm s$。(应该是我机子很垃圾，或者数据有点水分。)

然后我最开始的pushdown还调用了一个merge函数然后十秒都跑不完。

把merge函数删掉，然后我的要跑 $7.5\rm s$。怎么会是呢。

一看我原来的pushdown:

void push_up(int curnd)
{
    const auto& tmp=treap[curnd].sons;
    treap[curnd].size=treap[tmp[1]].size+1+treap[tmp[0]].size;
    for(unsigned int i=0,tmp2=treap[curnd].val;i<=10;i++)
        treap[curnd].answers[i]=treap[tmp[0]].answers[i]+tmp2,tmp2*=treap[tmp[0]].size+1;
    for(int i=0;i<=10;i++)
        for(unsigned int j=0,tmp2=1;j<=i;j++)
            treap[curnd].answers[i]+=binoms[i][j]*tmp2*treap[tmp[1]].answers[i-j],
            tmp2*=treap[tmp[0]].size+1;
}

可以看到，里面多次调用了treap[tmp[0]].size和treap[tmp[1]].answers，这样内存访问跨度就不是一般的大，于是每次查询就会出现 $\mathrm O(k^2\log n)$ 个 cache miss。

然后改成这样：

void push_up(int curnd)
{
    const auto& tmp=treap[curnd].sons;
    const unsigned int lsonsize=treap[tmp[0]].size+1;
    treap[curnd].size=treap[tmp[1]].size+1+treap[tmp[0]].size;
    tmpans=treap[tmp[0]].answers;
    for(unsigned int i=0,tmp2=treap[curnd].val;i<=10;i++)
        treap[curnd].answers[i]=tmpans[i]+tmp2,tmp2*=lsonsize;
    tmpans=treap[tmp[1]].answers;
    for(int i=0;i<=10;i++)
        for(unsigned int j=0,tmp2=1;j<=i;j++)
            treap[curnd].answers[i]+=binoms[i][j]*tmp2*tmpans[i-j],
            tmp2*=lsonsize;
}

直接跑到了 $4\rm s$。交上去过了。