其实这道题分块也可以水过
将色板分成 $\sqrt(N)$ 块，块内维护是否被标记和涂有几种颜色
每次更新和查询时整块直接查询，块内暴力查询，复杂度 $M\sqrt(N) \T$
```cpp
#include <algorithm>
#include <iostream>
#include <fstream>
#include <cstring>
#include <cstdlib>
#include <string>
#include <cstdio>
#include <vector>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <map>
using namespace std;
struct block
{
int l;
int r;
int v;
bool c[40];
};
const int MAXN = 1e5 + 100;
int n, m, T, size;
int a[MAXN], g[MAXN];
block b[500];
void update(int p)
{
int l = b[p].l, r = b[p].r;
memset(b[p].c, 0, sizeof b[p].c);
if (b[p].v != 0)
{
for (int i = l; i < r + 1; ++i)
a[i] = b[p].v;
b[p].v = 0;
}
for (int i = l; i < r + 1; ++i)
b[p].c[a[i]] = true;
return;
}
void paint(int l, int r, int x)
{
int beg = g[l], end = g[r];
if (beg == end)
{
update(beg);
for (int i = l; i < r + 1; ++i)
a[i] = x;
update(beg);
}
else
{
update(beg);
for (int i = l; i < beg * size + 1; ++i)
a[i] = x;
update(beg);
update(end);
for (int i = (end - 1) * size + 1; i < r + 1; ++i)
a[i] = x;
update(end);
for (int i = beg + 1; i < end; ++i)
b[i].v = x;
}
return;
}
int query(int l, int r)
{
int beg = g[l], end = g[r], ret = 0;
bool h[40];
memset(h, 0, sizeof h);
if (beg == end)
{
update(beg);
for (int i = l; i < r + 1; ++i)
{
if (!h[a[i]])
h[a[i]] = true;
}
}
else
{
update(beg);
for (int i = l; i < beg * size + 1; ++i)
{
if (!h[a[i]])
h[a[i]] = true;
}
update(end);
for (int i = (end - 1) * size + 1; i < r + 1; ++i)
{
if (!h[a[i]])
h[a[i]] = true;
++ret;
}
for (int i = beg + 1; i < end; ++i)
{
if (b[i].v == 0)
{
for (int j = 1; j < T + 1; ++j)
{
if (b[i].c[j] && !h[j])
h[j] = true;
}
}
else if (!h[b[i].v])
h[b[i].v] = true;
}
}
ret = 0;
for (int i = 1; i < T + 1; ++i)
{
if (h[i])
++ret;
}
return ret;
}
inline int read()
{
char ch = getchar();
while (ch < '0' || ch > '9')
ch = getchar();
int x = 0;
while (ch >= '0' && ch <= '9')
{
x = x * 10 + ch - '0';
ch = getchar();
}
return x;
}
int main()
{
n = read();
T = read();
m = read();
size = sqrt(n) + 1;
for (int i = 1; i < n + 1; ++i)
{
a[i] = 1;
g[i] = (i - 1) / size + 1;
}
for (int i = 1; i < size + 1; ++i)
{
b[i].v = 0;
b[i].c[1] = true;
b[i].l = (i - 1) * size + 1;
b[i].r = i * size;
}
for (int i = 0; i < m; ++i)
{
char ch = getchar();
while (ch != 'C' && ch != 'P')
ch = getchar();
if (ch == 'C')
{
int l = read(), r = read(), x = read();
if (l > r)
swap(l, r);
paint(l, r, x);
}
else if (ch == 'P')
{
int l = read(), r = read();
if (l > r)
swap(l, r);
printf("%d\n", query(l, r));
}
}
return 0;
}
```