HDU 5997 rausen loves cakes （启发式合并+树状数组）

问题描述 rausen喜欢吃蛋糕。某天，他买了$n$个蛋糕，每个蛋糕都有一个颜色，用$\left[1,1000000\right]$中的整数来表示。rausen将它们从左到右排成一行，然后准备开始吃。 在吃之前，rausen想对蛋糕进行$q$个操作。 某些时刻，rausen会把所有颜色为$x$的蛋糕替换成颜色为$y$的蛋糕。 另一些时刻，rausen会计算一段区间$\left[x,y\right]$内颜色的段数，所谓一段颜色，就是指极长的只有一种颜色的区间。例如1 4 4 1 1即为3段颜色。 然而，rausen发现，他并不会统计区间内的颜色段数，无助的rausen伤心地哭了起来（误）。而你为了安慰他，决定帮他解决这个问题。 输入描述 输入包含多组数据。第一行有一个整数$T$，表示测试数据的组数，对于每组数据： 第一行输入2个整数$n$，$q$分别表示蛋糕的数目和操作的数目。 接下来一行$n$个正整数，第$i$个正整数{a}_{i}a​i​​表示第$i$个蛋糕的颜色。 接下来$q$行，每行3个整数$op\left(1\le op\le 2\right)$，$x$，$y$，描述一个操作 对于$op=1$，表示rausen进行替换操作，将颜色为$x$的蛋糕替换成颜色为$y$的蛋糕，$x$、$y$满足$\left(1\le x,y\le 1000000\right)$，请注意$x$可能等于$y$。 对于$op=2$，表示rausen进行计数操作，此时你需要输出区间$\left[x,y\right]$内颜色的段数，$x$、$y$满足$\left(1\le x\le y\le n\right)$ $\left(1\le T\le 5\right)$，\left(1\leq n\leq {10}^{5} \right)(1≤n≤10​5​​)，\left(1\leq q\leq {10}^{5} \right)(1≤q≤10​5​​) 输出描述 对于每组测试数据的每一个计数操作，单独输出一行表示答案。 输入样例 1 5 3 1 4 4 10 1 2 1 5 1 4 10 2 3 5 输出样例 4

2

替换颜色的时候可以采用启发式合并，把小的往大的里面塞，然后记住每个颜色在当前序列中的颜色，然后维护一个树状数组，统计相邻位置的情况即可。

此题与梦幻布丁一样，不懂的话可以先去看 bzoj1483这道题。 这里讲的很好，可以点进去看看-->bzoj1483 （hnoi2009）梦幻布丁（链表+启发式合并） 

代码：参考_Occult_

#include<cmath> #include<queue> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; #define ms(x,y) memset(x,y,sizeof(x)) #define rep(i,j,k) for(int i=j;i<=k;i++) #define loop(i,j,k) for (int i=j;i!=-1;i=k[i]) #define inone(x) scanf("%d",&x) #define intwo(x,y) scanf("%d%d",&x,&y) #define inthr(x,y,z) scanf("%d%d%d",&x,&y,&z) #define lson x<<1,l,mid #define rson x<<1|1,mid+1,r typedef long long LL; const int low(int x) { return x&-x; } const int mod = 1e9 + 7; const int N = 1e6 + 10; int T, n, m, x, y, z; int ft[N], nt[N], u[N], sz; int f[N], g[N], a[N], q[N]; void add(int x, int y) { for (int i = x; i <= n; i += low(i)) q[i] += y; } int sum(int x) { int s = 0; for (int i = x; i; i -= low(i)) s += q[i]; return s; } int main() { inone(T); while (T--) { intwo(n, m); ms(ft, -1); ms(f, 0); ms(g, 0); ms(q, 0); sz = 0; a[0] = a[n + 1] = -1; rep(i, 1, n) { inone(a[i]); f[a[i]] = a[i]; g[a[i]]++; u[sz] = i; nt[sz] = ft[a[i]]; ft[a[i]] = sz++; if (a[i] != a[i - 1]) add(i, 1); } while (m--) { inthr(x, y, z); if (x == 2) printf("%d\n", sum(z) - sum(y - 1) + (int)(a[y] == a[y - 1])); else { if (y == z || !g[f[y]]) continue; int s = y, t = z; if (g[f[y]] > g[f[z]]) swap(y, z); y = f[y]; z = f[z]; loop(i, ft[y], nt) { if (a[u[i]] != a[u[i] - 1]) add(u[i], -1); if (a[u[i]] != a[u[i] + 1]) add(u[i] + 1, -1); a[u[i]] = z; if (a[u[i]] != a[u[i] - 1]) add(u[i], 1); if (a[u[i]] != a[u[i] + 1]) add(u[i] + 1, 1); if (nt[i] == -1) { nt[i] = ft[z]; ft[z] = ft[y]; break; } } g[z] += g[y]; g[y] = 0; f[t] = z; f[s] = 0; } } } return 0; }