我的这份代码，树剖+可撤销并查集，没有线段树，没有树状数组，直接一个一个节点往上修改，居然能过！数据已经不是一点两点的水了！必须要修改！

下面是 HACK 数据生成器：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#include<stack>
using namespace std;
int n,m;
int main(){
	freopen("P4219.in","w",stdout);
	n=5e4,m=1e5;
	printf("%d %d\n",n,m);
	for(int i=1;i<n;i++){
		printf("A %d %d\n",i,i+1);
	}
	for(int i=n;i<=m;i++){
		printf("Q %d %d\n",n-1,n);
	}
}

当然如果直接需要数据，我也可以提供。