题意是支持两种操作：区间染色；询问区间[l,r]之间有多少个颜色是x的。

wulala的题解是这样写的

 

30分的话直接暴力，

60分对于每种宗教维护一颗线段树

100分的话分块就可以了，每次暴力处理起点和终点所在块，其他块打标记复杂度为n(sqrtn + m)或是nsqrtn具体复杂度看写法，为了降低难度两种都可以过。

我写的是很渣的线段树，就是一棵然后区间打上标记的那种

一开始觉得如果10w个不相同的数+10w个询问，这要T的

但是实际上因为是一个询问紧接着一个修改，而且是ask(l,r)之后change(l,r)，就是询问修改是同一个区间，实际上应该可以证明平摊复杂度不会很高

然后我只A了这题T T毕竟我很弱啊QAQ

#include
     
      struct segtree{	int l,r,len,tag;}tree[1000000];int a[100010];int n,m,k;inline int read(){    int x=0,f=1;char ch=getchar();    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}    return x*f;}inline void update(int now){	tree[now].tag=(tree[now<<1].tag+tree[now<<1|1].tag)/2;	if (tree[now<<1].tag!=tree[now<<1|1].tag)tree[now].tag=0;}inline void pushdown(int now){	if (!tree[now].tag)return;	tree[now<<1].tag=tree[now<<1|1].tag=tree[now].tag;}inline void buildtree(int now,int l,int r){	tree[now].l=l;tree[now].r=r;tree[now].len=r-l+1;	if (l==r)	{		tree[now].tag=a[l];		return;	}	int mid=(l+r)>>1;	buildtree(now<<1,l,mid);	buildtree(now<<1|1,mid+1,r);	update(now);}inline int find(int now,int x){	if (tree[now].tag)return tree[now].tag;	int l=tree[now].l,r=tree[now].r;	int mid=(l+r)>>1;	if(x<=mid)return find(now<<1,x);	else return find(now<<1|1,x);}inline void change(int now,int l,int r,int dat){	pushdown(now);	int x=tree[now].l,y=tree[now].r;	if (x==l&&y==r)	{		tree[now].tag=dat;		return;	}	int mid=(x+y)>>1;	if (r<=mid)change(now<<1,l,r,dat);	else if (l>mid)change(now<<1|1,l,r,dat);	else 	{		change(now<<1,l,mid,dat);		change(now<<1|1,mid+1,r,dat);	}	update(now);}inline int ask(int now,int l,int r,int dat){	pushdown(now);	int x=tree[now].l,y=tree[now].r;	if (x==l&&y==r)	{		if (tree[now].tag==dat)return tree[now].len;		if (tree[now].tag)return 0;	}	int mid=(x+y)>>1;	if (r<=mid)return ask(now<<1,l,r,dat);	else if (l>mid)return ask(now<<1|1,l,r,dat);	else return ask(now<<1,l,mid,dat)+ask(now<<1|1,mid+1,r,dat);	update(now);}int main(){	freopen("friend.in","r",stdin);	freopen("friend.out","w",stdout);	n=read();m=read();	for (int i=1;i<=n;i++)a[i]=read();	buildtree(1,1,n);	k=read();	for (int i=1;i<=k;i++)	{		int x=read(),y=read();		if (x==y){printf("0\n");continue;}		int typ=find(1,x);		printf("%d\n",ask(1,x,y,typ)-1);		change(1,x,y,typ);	}}