题目描述

给出一个长为 $n$ 的数列，以及 $n$ 个操作，操作涉及区间询问等于一个数 $c$ 的元素，并将这个区间的所有元素改为 $c$。

输入格式

第一行输入一个数字 $n$。

第二行输入 $n$ 个数字，第 i 个数字为 $a_i$，以空格隔开。

接下来输入 $n$ 行询问，每行输入三个数字 $l$、$r$、$c$，以空格隔开。

表示先查询位于 $[l,r]$ 的数字有多少个是 $c$，再把位于 $[l,r]$ 的数字都改为 $c$。

样例

输入：

4
1 2 2 
1 3 1
1 4 4
1 2 2
1 4 2

输出

1
1
0
2

Code

用分块做的。

#include<bits/stdc++.h>
using namespace std;
int a[100005],upd[10005],len;
//upd 表示该区间修改成 c，但未在原数组上修改，len 是块的大小。
const int INF=0xcfcfcfcf;
int gt(int x)//下标为 x 的属于哪个块。
{
	return (x-1)/len+1;
}
int query(int l,int r,int c)
{
	int ans=0;
	if(gt(l)==gt(r))//在同一个块内，暴力。
	{
		int st=gt(l);
		if(upd[st]==c) return r-l+1;
		for(int i=l;i<=r;i++)
		{
			if(a[i]==c)
				ans++;
			a[i]=c;
		}
		upd[st]=INF;
		return ans;
	}
	int st=gt(l),ed=gt(r);
	while(gt(l)==st)//处理首块
	{
		if(a[l]==c||upd[st]==c) ans++;
		a[l++]=c;
	}
	while(gt(r)==ed)//处理尾块
	{
		if(a[r]==c||upd[ed]==c) ans++;
		a[r--]=c;
	}
	upd[ed]=INF;
	upd[st]=INF;
	for(int i=gt(l);i<=gt(r);i++)//处理中间的块
	{
		if(upd[i]==c) ans+=len;
		else
		{
			if(upd[i]==INF)//删了这个 if TLE 30。
			{
				for(int j=(i-1)*len+1;j<=i*len;j++)
				{
					if(a[j]==c) ans++;
					a[j]=c;
				}
			}
		}
		upd[i]=c;	//删了这行 TLE 30。
     				//两个都不删 WA 0。
	}
	return ans;
}
int read() {
  int x = 0, w = 1;
  char ch = 0;
  while (ch < '0' || ch > '9') {  // ch 不是数字时
    if (ch == '-') w = -1;        // 判断是否为负
    ch = getchar();               // 继续读入
  }
  while (ch >= '0' && ch <= '9') {  // ch 是数字时
    x = (x<<3)+(x<<1) + (ch - '0');  // 将新读入的数字「加」在 x 的后面
    // x 是 int 类型，char 类型的 ch 和 '0' 会被自动转为其对应的
    // ASCII 码，相当于将 ch 转化为对应数字
    // 此处也可以使用 (x<<3)+(x<<1) 的写法来代替 x*10
    ch = getchar();  // 继续读入
  }
  return x * w;  // 数字 * 正负号 = 实际数值
}
void write(int x) {
  static int sta[35];
  int top = 0;
  do {
    sta[top++] = x % 10, x /= 10;
  } while (x);
  while (top) putchar(sta[--top] + 48);  // 48 是 '0'
}
signed main()
{ 
	memset(upd,0xcf,sizeof(upd));
	cin.tie(0);
	cout.tie(0);
	int n,l,r,c;
	n=read();
	len=sqrt(n);
	for(int i=1;i<=n;i++) a[i]=read();
	for(int i=1;i<=n;i++)
	{
		l=read(),r=read(),c=read();
		write(query(l,r,c));
		putchar('\n');
	}
	return 0;
}