[原创]hdu 5997 rausen loves cakes [启发式合并+树状数组/线段数]【杂类+数据结构】

2017-01-15 21:48:17 Tabris_ 阅读数：258

博客爬取于2020-06-14 22:42:09
以下为正文

版权声明：本文为Tabris原创文章，未经博主允许不得私自转载。
https://blog.csdn.net/qq_33184171/article/details/54564954

题目连接：http://acm.split.hdu.edu.cn/showproblem.php?pid=5997
----------------------------------------------------------------.
rausen loves cakes

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
问题描述
rausen喜欢吃蛋糕。某天，他买了nn个蛋糕，每个蛋糕都有一个颜色，用\left[1,1000000 \right][1,1000000]中的整数来表示。rausen将它们从左到右排成一行，然后准备开始吃。

在吃之前，rausen想对蛋糕进行qq个操作。

某些时刻，rausen会把所有颜色为xx的蛋糕替换成颜色为yy的蛋糕。

另一些时刻，rausen会计算一段区间\left[x,y \right][x,y]内颜色的段数，所谓一段颜色，就是指极长的只有一种颜色的区间。例如1 4 4 1 1即为3段颜色。

然而，rausen发现，他并不会统计区间内的颜色段数，无助的rausen伤心地哭了起来（误）。而你为了安慰他，决定帮他解决这个问题。
输入描述
输入包含多组数据。第一行有一个整数TT，表示测试数据的组数，对于每组数据：

第一行输入2个整数nn，qq分别表示蛋糕的数目和操作的数目。

接下来一行nn个正整数，第ii个正整数{a}_{i}a
i
表示第ii个蛋糕的颜色。

接下来qq行，每行3个整数op\left(1\leq op\leq 2 \right)op(1≤op≤2)，xx，yy，描述一个操作
对于op=1op=1，表示rausen进行替换操作，将颜色为xx的蛋糕替换成颜色为yy的蛋糕，xx、yy满足\left(1\leq x,y\leq 1000000 \right)(1≤x,y≤1000000)，请注意xx可能等于yy。

对于op=2op=2，表示rausen进行计数操作，此时你需要输出区间\left[x,y \right][x,y]内颜色的段数，xx、yy满足\left(1\leq x\leq y\leq n \right)(1≤x≤y≤n)

\left(1\leq T\leq 5 \right)(1≤T≤5)，\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
----------------------------------------------------------------.

藏了好久终于补了这个，虽然还是感觉有点乱乱的。。。。

首先考虑暴力的把一种颜色替换成另一种颜色,那么这一部分就是O(n)O(n)
那么考虑将每一种颜色所在的位置记录下来,这样的话就能降到O(颜色x的个数)O(颜色x的个数),虽然看着没什么提升,但其实已经提升很大了,
但是考虑颜色x−>颜色y颜色x->颜色y如果NUM(x) = n-1,NUM(y)=1,那么直接将x替换为y实在是太浪费了，于是可以将y替换成x，这样的话，运算量将大大减少。而且只需要用一个数组映射就能够实现。（这就是启发式合并了。。。）

用树状数组来维护拐点（ai!=ai+1a_{i} != a_{i+1} 那么aia_i就是一个拐点）
那么来统计区间内的颜色段数就是求区间内的拐点个数+左端点是不是拐点。。
维护这个就是简单的树状数组的操作了,不再赘述,其实用线段是也可以维护的,但是线段树的代码量…

代码中有详细点的注释,可以看看…

附本题代码
------------------------------------------------------------。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
# include <bits/stdc++.h>
using namespace std;
typedef long long int LL ;
/***********************************************************************/
const int N = 1000000 + 5;            //数列的大小
int ft[N];   //ft[a]=b 是a这个颜色最后一次出现的位置是b
int nt[N];   //nt[a]=b 是a这个位置的颜色上一次出现过的地方是b(因为修改 所以可能是乱序的,但是最终都是连在一起的)
int u[N];    //ft[],nt[] 维护的是一种颜色链之间的关系,所以我们需要一个u[]来表示在最初的位置
int cnt,n,q; //略
int f[N];    //f[a]=b ,颜色号为a的颜色 现在代表颜色b
int g[N];    //记录这个颜色即时的个数
int a[N];    //输入的数组值
int sum[N];  //树状数组
# define lowbit(x)  (x&(-x))         //lowbit操作
void update(int index,int val){     //单点更新  （+val）
    for(int i=index;i<=N;i+=lowbit(i))     sum[i]+=val;
}
int getSum(int index) {             //求解1~index的和
    int ans = 0;
    for (int i = index; i; i -= lowbit(i)) ans += sum[i];
    return ans;
}
/**
用树状数组来维护拐点（a_{i} !=  a_{i+1} 那么a_i就是一个拐点）
那么来统计区间内的颜色段数就是求区间内的拐点个数+左端点是不是拐点。。

采取启发式合并的方式来减少计算。
*/
int main(){
    int _ = 1;
    while(~scanf("%d",&_)){
        while(_--){
            scanf("%d %d",&n,&q);
            memset(ft,-1,sizeof(ft));
            memset(f,0,sizeof(f));
            memset(g,0,sizeof(g));
            memset(sum,0,sizeof(sum));
            cnt=0;a[0]=a[n+1]=-1;

            for(int i=1;i<=n;i++){
                scanf("%d",&a[i]);
                f[a[i]]=a[i];g[a[i]]++;u[++cnt]=i;nt[cnt]=ft[a[i]];ft[a[i]]=cnt;
                //printf("i=%d cnt=%d u[%d]=%d nt[%d]=%2d ft[%2d]=%d \n",i,cnt-1,cnt-1,u[cnt-1],cnt-1,nt[cnt-1],a[i],ft[a[i]]);
                if(a[i]!=a[i-1]) update(i,1);
            }
            int op,x,y;
            while(q--){
                scanf("%d%d%d",&op,&x,&y);
                if(1==op){
                    if(x==y||!g[f[x]]) continue;
                    int s=x,t=y;
                    if(g[f[x]]>g[f[y]]) swap(y,x);//将颜色少的改成颜色多的。  这就是启发式合并。。
                    x=f[x],y=f[y];
                    //printf("x=%d y=%d\n",x,y);
                    for(int j=ft[x];j!=-1;j=nt[j]){//然后一个一个判断增减。。。。
                        if (a[u[j]] != a[u[j] - 1]) update(u[j], -1);
                        if (a[u[j]] != a[u[j] + 1]) update(u[j] + 1, -1);
                        a[u[j]] = y;
                        if (a[u[j]] != a[u[j] - 1]) update(u[j], 1);
                        if (a[u[j]] != a[u[j] + 1]) update(u[j] + 1, 1);
                        if (nt[j] == -1)  {
                            nt[j] = ft[y]; ft[y] = ft[x]; break;  //将两段颜色的链连接起来.
                        }
                    }
                    g[y] += g[x]; g[x] = 0; f[t] = y; f[s] = 0; //这是颜色改变后的x，y的属性，（个数，代表的颜色）。
                }
                if(2==op)  printf("%d\n",getSum(y)-getSum(x-1)+(int)(a[x]==a[x-1]));
            }
        }
    }
    return 0;
}