这是原题

P1558是这道题的洛谷版。

经过我的检查，发现两者唯一的差别就是空间限制，洛谷版的是 $128\text{MB}$，而站外版的是 $64\text{MB}$。

我在洛谷提交的时候，提交记录显示这道题是过了所有点的，但是在站外提交的时候：

显示了TLE。

源码放在这个地方，求助万能的谷民，应该怎么办？

思路：开 $30$ 棵线段树，其中线段树 $k$ 代表颜色 $k$，维护的是某个区间共有多少个颜色 $k$。

源代码：

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
using namespace std;
#define lson l,mid,rt<<1
#define rson mid+1,r,(rt<<1)|1
#define rr(x) (x<<1)|1
#define ll(x) x<<1
int Len,T,O;
//不是哥们,真就30棵线段树呗
const int N=100010;
int sum[32][N<<2],lazy[32][N<<2];
void pushup(int id,int rt){
	sum[id][rt]=sum[id][rt<<1]+sum[id][(rt<<1)|1];
}
void pushdown(int id,int x)
{
	if (lazy[id][x]==-1) {
		sum[id][ll(x)]=sum[id][rr(x)]=0;
		lazy[id][ll(x)]=lazy[id][rr(x)]=-1;
	}
	else {
		sum[id][ll(x)]=sum[id][rr(x)]=lazy[id][x];
		lazy[id][ll(x)]=lazy[id][rr(x)]=lazy[id][x];
	}
	lazy[id][x]=0;
}
void build(int id,int l,int r,int rt){
	if(l==r){
		sum[id][rt]=1;
		return;
	}
	int mid=(l+r)>>1;
	build(id,lson);
	build(id,rson);
	pushup(id,rt);
}
void update(int id,int L,int R,int val,int l,int r,int rt){
	if(L<=l&&r<=R){
		sum[id][rt]=val;
		lazy[id][rt]=(val==0?-1:val);
		return;
	}
	int mid=(l+r)>>1;
	if(lazy[id][rt]){
		pushdown(id,rt);
	}
	if(L<=mid){
		update(id,L,R,val,lson);
	}
	if(R>mid){
		update(id,L,R,val,rson);
	}
	pushup(id,rt);
}
int query(int id,int L,int R,int l,int r,int rt){
	if(L<=l&&r<=R){
		return sum[id][rt];
	}
	int mid=(l+r)>>1;
	int res=0;
	if(lazy[id][rt]){
		pushdown(id,rt);
	}
	if(L<=mid){
		res+=query(id,L,R,lson);
	}
	if(R>mid){
		res+=query(id,L,R,rson);
	}
	return res;
}
int main(){
	scanf("%d%d%d",&Len,&T,&O);
	build(1,1,Len,1);
	int l,r,val;
	char c;
	while(O--){
		cin>>c;
		scanf("%d%d",&l,&r);
		if(l>r){
			swap(l,r);
		}
		if(c=='C'){//operation:change
			scanf("%d",&val);
			for(int i=1;i<=T;++i){
				update(i,l,r,(val==i),1,Len,1);
			}
		}
		else{
			int ans=0;
			for(int i=1;i<=T;++i){
				int tmp=query(i,l,r,1,Len,1);
				if(tmp>0){
					++ans;
				}
			}
			printf("%d\n",ans);
		}
	}
	return 0;
}