这个题本人调了两天，因为不希望把这份痛苦留给别人，在此公开一些可能对您有用的东西

首先是三组 hack 数据：

1.in

5 1
3 3 3 3 3
2 1
3 1
4 1
5 4
Q 4 5

1.out

1

2.in

5 1
2 3 2 1 1 
2 1
3 2
4 2
5 2
Q 1 3

2.out

3

3.in

5 2
2 1 1 2 3 
2 1
3 1
4 3
5 2
C 2 4 1
Q 2 3

3.out

1

若不正确请着重检查剖分查询，线段树查询，线段树更新部分

然后是对拍程序：

#include<bits/stdc++.h>
#define int long long
#define ll long long 
#define ull unsigned long long 
#define ldb long double
#define LS p<<1
#define RS p<<1|1
#define loop(ii,xx,yy) for(auto ii=xx;ii<=yy;ii++)
#define doop(ii,xx,yy) for(auto ii=xx;ii>=yy;ii--)
using namespace std;
ll read(){ll x=0,y=1;char ch=getchar();while((ch<'0'||ch>'9')&&ch!=EOF){if(ch=='-') y=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+(ch^48);	ch=getchar();}return x*y;}
const int Mod=998244353;
const int INF=0x3f3f3f3f;
const long long N=1e6+5;
const long long M=1e5+5;
ll n,m;
int randint(int x,int y){return rand()%(y-x+1)+x;}
int fa[N];
signed main(){
	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
	while(1){
		system("mk.exe > a.in");
		system("sb.exe < a.in > sb.out");
		system("nb.exe < a.in > nb.out");
		if(system("fc nb.out sb.out")){
			break;
		}
	}
	return 0;
}

数据生成程序：

#include<bits/stdc++.h>
#define int long long
#define ll long long 
#define ull unsigned long long 
#define ldb long double
#define LS p<<1
#define RS p<<1|1
#define loop(ii,xx,yy) for(auto ii=xx;ii<=yy;ii++)
#define doop(ii,xx,yy) for(auto ii=xx;ii>=yy;ii--)
using namespace std;
ll read(){ll x=0,y=1;char ch=getchar();while((ch<'0'||ch>'9')&&ch!=EOF){if(ch=='-') y=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+(ch^48);	ch=getchar();}return x*y;}
const int Mod=998244353;
const int INF=0x3f3f3f3f;
const long long N=1e6+5;
const long long M=1e5+5;
ll n,m;
int randint(int x,int y){return rand()%(y-x+1)+x;}
int fa[N];
bool con[N];
signed main(){
	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
	srand(time(NULL));
	n=randint(5,5),m=randint(2,4);
	printf("%lld %lld\n",n,m);
	loop(i,1,n){
		printf("%d ",randint(1,3));
	}
	printf("\n");
	loop(i,2,n){
		fa[i]=i;
		while(fa[i]==i)
			fa[i]=randint(1,i-1);
	}
	loop(i,2,n){
		printf("%d %d\n",i,fa[i]);
	}
	loop(i,1,m){
		if(rand()%2){
			int l=randint(1,n);
			int r=randint(l,n);
			printf("C %d %d %d\n",l,r,randint(1,3));
		}else{
			int l=randint(1,n);
			int r=randint(l,n);
			printf("Q %d %d\n",l,r);
		}
	}
	return 0;
}

其中 mk 为数据生成，sb 与 nb 分别为您的代码与一篇正解代码

希望您早日脱离苦海！