TLE #8 #9 #10

改了一下午,已经改的跟题解差不多了,但还是T

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,m,tt,qq;
int st[1145140];
int a[254154];
int b[254154];
struct N
{
	int l,r,t;
	int id;
} q[254154];
struct Change
{
	int x,c;
} p[254154];
char op;
int l,r,id,t;
int ans[254514];
int len;
int ln,rn,tn;
int res;

inline bool cmp(const N &x,const N &y)
{
	if(b[x.l]!=b[y.l])
	  return x.l<y.l;
	else
	{
		if(b[x.r]!=b[y.r])
		  return x.r<y.r;
		else  
		  x.t<y.t;
	}  
}
//return (belong[a.l] ^ belong[b.l]) ? belong[a.l] < belong[b.l] : ((belong[a.r] ^ belong[b.r]) ? belong[a.r] < belong[b.r] : a.time < b.time);

int main()
{
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	  cin>>a[i];
	while(m--)
	{
		cin>>op;
		if(op=='Q')
		{
			cin>>q[++qq].l>>q[qq].r;
			q[qq].id=qq;
			q[qq].t=tt;
		}
		else
		{
			cin>>p[++tt].x>>p[tt].c;
		//	cout<<m<<' ';
		  //cout<<t<<' ';
		}	
	}
	
	len=cbrt(n*n);
  for(int i=1;i<=n;i++)
	{
		op=(i-1)/len+1;
		b[i]=op;
	}
	sort(q+1,q+1+qq,cmp);
	
	ln=1,rn=0,tn=0;
	for(int i=1;i<=qq;i++)
	{
		l=q[i].l,r=q[i].r,t=q[i].t;
		id=q[i].id;
		
		while(ln<l)
		{
			st[a[ln]]--;
			  res-=!st[a[ln++]];
		}
		while(ln>l)
		{
			  res+=!st[a[--ln]];	
				st[a[ln]]++;  
		}
		while(rn<r)
		{
			res+=!st[a[++rn]];
			st[a[rn]]++;
		}
		while(rn>r)
		{
			st[a[rn]]--;
			res-=!st[a[rn--]];
		}
		while(tn<t)
		{	
		  tn++;	
			int aa=p[tn].x,bb=p[tn].c;
			if(ln<=aa&&aa<=rn)
			{
				st[a[aa]]--;
				res-=!st[a[aa]];
				res+=!st[bb];
				st[bb]++;
			}	
			swap(a[aa],p[tn].c);  
		}
		while(tn>t)
		{
			int aa=p[tn].x,bb=p[tn].c;
			if(ln<=aa&&aa<=rn)
			{
				st[a[aa]]--;
				  res-=!st[a[aa]];
				  res+=!st[bb];
				st[bb]++;
			}
			swap(a[aa],p[tn].c);	
			tn--;
		}
		ans[id]=res;	
		//cout<<ln<<' '<<rn<<'\n';
	}
	for(int i=1;i<=qq;i++)
	  cout<<ans[i]<<'\n';
	
	return 0;
}