这题细节比较多，有些东西我没办法给一个准确的提醒，我是用块状链表写的，同样方法的可以尝试把分裂操作去掉跑的更快（虽然我也不知道为什么），其他就是一些细节问题。

这题静态查错难度较大，所以我在这里帮大家提供了对拍程序供大家使用。

使用时把强制在线的部分去掉（即异或部分）。

随机数生成器：

#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<queue>
#include<cmath>
#include<string>
#include<algorithm>
#include<functional>
#include<numeric>
#include<math.h>
using namespace std;
const int N=750;
int n;
int main()
{
	srand(time(0));
	cout<<N<<endl;
	for(int i=1;i<=N;i++)
	{
		cout<<rand()%(N+1)<<" ";
	}
	cout<<endl;
	cout<<N<<endl;
	n=N;
	for(int i=1;i<=N;i++)
	{
		int x=rand();
		if(x%3==0)
		{
			cout<<"Q ";
			int l=rand()%n+1,r=rand()%n+1;
			if(l>r)
			{
				swap(l,r);
			}
			int k=rand()%(r-l+1)+1;
			cout<<l<<" "<<r<<" "<<k<<endl;
		}
		else if(x%3==1)
		{
			cout<<"I ";
			n++;
			int x=rand()%n+1,val=rand()%(N+1);
			cout<<x<<" "<<val<<endl;
		}
		else
		{
			cout<<"M ";
			int x=rand()%n+1,val=rand()%(N+1);
			cout<<x<<" "<<val<<endl;
		}
	}
}

暴力程序：

#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<queue>
#include<cmath>
#include<string>
#include<algorithm>
#include<functional>
#include<numeric>
#include<math.h>
using namespace std;
int n,a[100010],m,c[100010];
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
	}
	cin>>m;
	while(m--)
	{
		char op;
		cin>>op;
		if(op=='Q')
		{
			int l,r,k;
			cin>>l>>r>>k;
			int len=0;
			for(int i=l;i<=r;i++)
			{
				c[++len]=a[i];
			}
			sort(c+1,c+len+1);
			cout<<c[k]<<endl;
		}
		else if(op=='M')
		{
			int x,val;
			cin>>x>>val;
			a[x]=val;
		}
		else
		{
			int x,val;
			cin>>x>>val;
			n++;
			for(int i=x;i<=n;i++)
			{
				swap(val,a[i]);
			}
		}
	}
	return 0;
}

如需要调整数据范围可以自行调整。