asp网站打开,广平专业做网站,哈尔滨企业制作网站,外贸网站外链平台Description N个布丁摆成一行,进行M次操作.每次将某个颜色的布丁全部变成另一种颜色的,然后再询问当前一共有多少段颜色.例如颜色分别为1,2,2,1的四个布丁一共有3段颜色. Input 第一行给出N,M表示布丁的个数和好友的操作次数. 第二行N个数A1,A2...An表示第i个布丁的颜色从第三行…Description N个布丁摆成一行,进行M次操作.每次将某个颜色的布丁全部变成另一种颜色的,然后再询问当前一共有多少段颜色.例如颜色分别为1,2,2,1的四个布丁一共有3段颜色. Input 第一行给出N,M表示布丁的个数和好友的操作次数. 第二行N个数A1,A2...An表示第i个布丁的颜色从第三行起有M行,对于每个操作,若第一个数字是1表示要对颜色进行改变其后的两个整数X,Y表示将所有颜色为X的变为YX可能等于Y. 若第一个数字为2表示要进行询问当前有多少段颜色这时你应该输出一个整数. 0 Output 针对第二类操作即询问依次输出当前有多少段颜色. Sample Input 4 3 1 2 2 1 2 1 2 1 2 Sample Output 3 1 题解 用链表来更好的遍历每种颜色 暴力遍历算对答案的贡献 合并时用启发式合并 就是如果s[b]s[a] 就把b和入a 但是把a和b真实对应的颜色改一下(很常用的技巧) 那么对于最不好的情况 也就是每次s[b]s[a] 合并时 s扩大logn次 如果把同一个s级别的一起看 每次O(n) 所以最坏时间复杂度O(nlogn) 虽然这道题不用启发式合并速度也差不多(但就要注意b为空的情况了 启发式合并可以直接避免) 再次记一下合并链表步骤(合a入b) next[b尾]a首b首a首清空a 代码 #includecstdio
#includealgorithm
using namespace std;
const int N1e55,M1e65;int c[N],next[N],head[M],last[M],p[M],s[M];
int n,m,ans;int solve(int a,int b){s[b]s[a];s[a]0;for(int ilast[a];i;inext[i]){if(c[i-1]b) ans--;if(c[i1]b) ans--;}for(int ilast[a];i;inext[i]) c[i]b;next[head[b]]last[a];head[b]head[a];last[a]head[a]0;
}int main(){scanf(%d%d,n,m);for(int i1;in;i){scanf(%d,c[i]);p[c[i]]c[i];s[c[i]];if(c[i]!c[i-1]) ans;if(!last[c[i]]) head[c[i]]i;next[i]last[c[i]];last[c[i]]i;}int x,a,b;for(int i1;im;i){scanf(%d,x);if(x1){scanf(%d%d,a,b);if(ab) continue;if(s[p[a]]s[p[b]]) swap(p[a],p[b]);ap[a];bp[b];if(!s[a]) continue;solve(a,b);}else printf(%d\n,ans);}return 0;
} View Code 转载于:https://www.cnblogs.com/xkui/p/4535512.html
