时隔 $n$ 年重新来做这道神题，不是树剖已死，而是 hack 数据有问题！

题目中有这样一句话：

修改操作不超过10000个。

然后我 assert 了一发，代码。

这很重要，因为修改是双 $\log$ ，查询是单 $\log$ ， $4\cdot 10^4\cdot m\log^2 n\approx 10^9$ 在 3s 时限下还有救。

根据LOJ 上的 hack稍微改了一下，应该能卡掉一些实现极劣的树剖。

#include<bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define pii pair<int,int>
using namespace std;
const int maxn=3e4+5;
int m,n,q,cnt;
vector<pii> edge;
auto seed=chrono::high_resolution_clock::now().time_since_epoch().count();
mt19937 rnd(seed);
void gen_chain(int fa, int len)
{
    vector<int> id={fa};
    for(int i=1;i<=len;i++) id.push_back(++n);
    for(int i=1;i<id.size();i++)
        if(id[i-1])
            edge.push_back(mp(id[i-1],id[i]));
    if(id.size()>=2) gen_chain(id[1],(len-1)/2);
}
int main()
{
    freopen("data.in","w",stdout);
    m=128,q=3e4,gen_chain(0,15010);
    printf("%d %d\n",n,m);
    for(int i=1;i<=n;i++) printf("%d ",rnd()%m);
    putchar('\n');
    for(auto p:edge) printf("%d %d\n",p.fi,p.se);
    printf("%d\n",q);
    for(int i=1;i<=q;i++)
        if(rnd()%3==0&&cnt<10000) printf("Change %d %d\n",rnd()%n+1,rnd()%m),cnt++;
        else printf("Query %d\n",rnd()%n+1);
    return 0;
}

建议管理把之前的 hack 撤下，把上面的 hack 加上；后人亦可用上述代码进行自测。

随机树剖懒得卡了。