题解 P1558 【色板游戏】

· · 题解

题目传送门

分块真是万能……

这道题各位巨佬用了各种方式,我就在这提供一种比较简单易懂的分块方法。

分块维护一个序列的颜色,时间复杂度比较稳定,就算颜色增加,

会变的只有\texttt{memset(vis,0,sizeof vis)}

个人认为还是一种比较好的方法。

--- ```cpp #include <cmath> #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; template<typename T>void read(T &x) { T f = 1;x = 0;char s = getchar(); while(s < '0' || s > '9') {if(s == '-')f = -1;s = getchar();} while(s >= '0' && s <= '9') {x = x * 10 + s - '0';s = getchar();} x *= f; } template<typename T>void print(T x) { if(x < 0) putchar('-'),x = -x; if(x > 9) print(x / 10); putchar(x % 10 + '0'); } const int maxn = 100005; int n,t,m; int pos[maxn],res[maxn * 10],L[maxn],R[maxn]; int vis[40],sum[maxn],a[maxn]; void update(int l,int r,int z) { int p = pos[l],q = pos[r]; if (sum[p]) for (int i = L[p] ; i <= R[p] ; ++ i) a[i] = sum[p]; sum[p] = 0; if (sum[q]) for (int i = L[q] ; i <= R[q] ; ++ i) a[i] = sum[q]; sum[q] = 0; if (p == q) for (int i = l ; i <= r ; ++ i) a[i] = z; else { for (int i = l ; i <= R[p] ; ++ i) a[i] = z; for (int i = L[q] ; i <= r ; ++ i) a[i] = z; for (int i = p + 1 ; i <= q - 1 ; ++ i) sum[i] = z; } } int solve(int x) { int res = 0; for (int i = L[x] ; i <= R[x] ; ++ i) res += vis[a[i]] ++ == 0; return res; } int query(int l,int r) { int p = pos[l],q = pos[r],res = 0; if (sum[p]) for (int i = L[p] ; i <= R[p] ; ++ i) a[i] = sum[p]; sum[p] = 0; if (sum[q]) for (int i = L[q] ; i <= R[q] ; ++ i) a[i] = sum[q]; sum[q] = 0; if (p == q) for (int i = l ; i <= r ; ++ i) res += vis[a[i]] ++ == 0; else { for (int i = l ; i <= R[p] ; ++ i) res += vis[a[i]] ++ == 0; for (int i = L[q] ; i <= r ; ++ i) res += vis[a[i]] ++ == 0; for (int i = p + 1 ; i <= q - 1 ; ++ i) if (!sum[i]) res += solve(i);else res += vis[sum[i]] ++ == 0; } return res; } int main() { read(n);read(t);read(m); int t = sqrt(n); for (int i = 1 ; i <= t ; ++ i) { L[i] = R[i - 1] + 1; R[i] = i * t; } if (R[t] != n) ++ t,L[t] = R[t - 1] + 1,R[t] = n; for (int i = 1 ; i <= t ; ++ i) for (int j = L[i] ; j <= R[i] ; ++ j) pos[j] = i; for (int i = 1 ; i <= n ; ++ i) { a[i] = 1; sum[pos[i]] = 1; } char s[4]; int x,y,z; for (int i = 1 ; i <= m ; ++ i) { scanf("%s",s); read(x);read(y); if (x > y) swap(x,y); if (*s == 'C') { read(z); update(x,y,z); } else { memset(vis,0,sizeof vis); printf("%d\n",query(x,y)); } } return 0; } ```