当前位置：首页 > news >正文

打卡信奥刷题（2789）用C++实现信奥题 P3939 数颜色

news 2026/5/11 10:02:18

P3939 数颜色

题目背景

大样例可在页面底部「附件」中下载。

题目描述

小 C 的兔子不是雪白的，而是五彩缤纷的。每只兔子都有一种颜色，不同的兔子可能有相同的颜色。小 C 把她标号从 1 到n nn的n nn只兔子排成长长的一排，来给他们喂胡萝卜吃。排列完成后，第i ii只兔子的颜色是a i a_iai。

俗话说得好，“萝卜青菜，各有所爱”。小 C 发现，不同颜色的兔子可能有对胡萝卜的不同偏好。比如，银色的兔子最喜欢吃金色的胡萝卜，金色的兔子更喜欢吃胡萝卜叶子，而绿色的兔子却喜欢吃酸一点的胡萝卜……为了满足兔子们的要求，小 C 十分苦恼。所以，为了使得胡萝卜喂得更加准确，小 C 想知道在区间[ l j , r j ] [l_j,r_j][lj,rj]里有多少只颜色为c j c_jcj的兔子。

不过，因为小 C 的兔子们都十分地活跃，它们不是很愿意待在一个固定的位置；与此同时，小 C 也在根据她知道的信息来给兔子们调整位置。所以，有时编号为x j x_jxj和x j + 1 x_j+1xj+1的两只兔子会交换位置。小 C 被这一系列麻烦事给难住了。你能帮帮她吗？

输入格式

从标准输入中读入数据。输入第 1 行两个正整数n nn,m mm。

输入第 2 行n nn个正整数，第i ii个数表示第i ii只兔子的颜色a i a_iai。

输入接下来m mm行，每行为以下两种中的一种：

“1 l j r j c j 1\ l_j\ r_j\ c_j1ljrjcj” ：询问在区间[ l j , r j ] [l_j,r_j][lj,rj]里有多少只颜色为c j c_jcj的兔子；
“2 x j 2\ x_j2xj”：x j x_jxj和x j + 1 x_j+1xj+1两只兔子交换了位置。

输出格式

输出到标准输出中。

对于每个 1 操作，输出一行一个正整数，表示你对于这个询问的答案。

输入输出样例 #1

输入 #1

6 5 1 2 3 2 3 3 1 1 3 2 1 4 6 3 2 3 1 1 3 2 1 4 6 3

输出 #1

1 2 2 3

说明/提示

【样例 1 说明】

前两个 1 操作和后两个 1 操作对应相同；在第三次的 2 操作后，3 号兔子和 4 号兔子

交换了位置，序列变为 1 2 2 3 3 3。

【数据范围与约定】

子任务会给出部分测试数据的特点。如果你在解决题目中遇到了困难，可以尝试只解决一部分测试数据。对于所有测试点，有1 ≤ l j < r j ≤ n , 1 ≤ x j < n 1 \le l_j < r_j \le n,1 \le x_j < n1≤lj<rj≤n,1≤xj<n。每个测试点的数据规模及特点如下表：

特殊性质 1：保证对于所有操作 1，有∣ r j − l j ∣ ≤ 20 |r_j - l_j| \le 20∣rj−lj∣≤20或∣ r j − l j ∣ ≤ n − 20 |r_j - l_j| \le n - 20∣rj−lj∣≤n−20。

特殊性质 2：保证不会有两只相同颜色的兔子。

C++实现

#include<iostream>#include<cstdio>#include<cstring>#include<cmath>#include<vector>#include<algorithm>usingnamespacestd;intread(){intw=1,x=0,ch=getchar();for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')w=-1;for(;ch>='0'&&ch<='9';ch=getchar())x=x*10+ch-'0';returnx*w;}constintMAXN=(int)3e5+100;intn,m,a[MAXN];vector<int>q[MAXN];intopt,l,r,x;intmain(){n=read(),m=read();for(inti=1;i<=n;i++){a[i]=read();q[a[i]].push_back(i);}while(m--){opt=read();if(opt==1){l=read(),r=read(),x=read();intptr_l=lower_bound(q[x].begin(),q[x].end(),l)-q[x].begin();intptr_r=upper_bound(q[x].begin(),q[x].end(),r)-q[x].begin()-1;if(ptr_l>ptr_r){printf("0\n");continue;}printf("%d\n",ptr_r-ptr_l+1);}else{x=read();if(a[x]==a[x+1])continue;intptr_l=lower_bound(q[a[x]].begin(),q[a[x]].end(),x)-q[a[x]].begin();q[a[x]][ptr_l]++;intptr_r=lower_bound(q[a[x+1]].begin(),q[a[x+1]].end(),x+1)-q[a[x+1]].begin();q[a[x+1]][ptr_r]--;swap(a[x],a[x+1]);}}return0;}