题目大意:有n个物品,每个物品有一个颜色。现在有两种操作:1.查询l~r内有多少颜色为c的物品并输出。2.将第x个物品和第x+1个交换。现在让你实现这些操作。
解题思路:首先一共有300000种颜色,最多只有300000个物品,但如果直接开数组,结果可想而知。
所以考虑用vector保存每种颜色的编号。
并且我们保证每个vector里的值都是升序的。
首先考虑操作2。如果两个相邻的物品的位置交换,只要它们的颜色不同,则在vector中交换两个元素时,仍然保持升序。
那么如果颜色相同,就不用交换了,否则需要交换两个物品的颜色,并且在vector中也交换。
由于vector中是升序的,所以可以用二分查找(lower_bound)的方法找到两个物品的迭代器,然后交换里面的值即可。
对于操作1,很容易想到用vector右边的指针减去左边的指针。那么用二分出两个迭代器,然后相减即可。
总时间复杂度$O(mlog n)$。
C++ Code:
#include<cstdio> #include<vector> #include<cctype> #include<algorithm> using namespace std; #define N 300005 #define vt vector<int>::iterator int n,m,a[N]; vector<int>p[N]; inline int readint(){ char c=getchar(); for(;!isdigit(c);c=getchar()); int d=0; for(;isdigit(c);c=getchar()) d=(d<<3)+(d<<1)+(c^'0'); return d; } int main(){ n=readint(),m=readint(); for(int i=1;i<=n;++i)p[a[i]=readint()].push_back(i); while(m--){ int cz=readint(); if(cz==2){ int x=readint(); if(a[x]==a[x+1])continue; vt p1=lower_bound(p[a[x]].begin(),p[a[x]].end(),x), p2=lower_bound(p[a[x+1]].begin(),p[a[x+1]].end(),x+1); *p1=x+1,*p2=x; int f=a[x]; a[x]=a[x+1],a[x+1]=f; }else{ int l=readint(),r=readint(),c=readint(); vt l1=lower_bound(p[c].begin(),p[c].end(),l), r1=upper_bound(p[c].begin(),p[c].end(),r); printf("%d ",r1-l1); } } return 0; }