传送门
题目大意：
给定一个序列，维护每个数字在[L,R]出现的次数以及交换a[x]和a[x+1]的操作
一开始想的分桶法，感觉复杂度还可以吧，常数有点大，于是死得很惨（65分）
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<map>
#include<set>
#include<queue>
#include<vector>
#define INF 0x7f7f7f7f
#define pii pair<int,int>
#define ll long long
#define SIZE 2505
#define MAXN 300005
using namespace std; int read(){
int x=,f=;char ch=getchar();
while(ch<''||ch>''){if('-'==ch)f=-;ch=getchar();}
while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}
return x*f;
}
int n,num,len;
struct Bucket{
int L;
int a[SIZE];
vector<int> v;
Bucket(){
L=-;
memset(a,,sizeof(a));
}
void add(int x){
a[++L]=x;
vector<int>::iterator P=lower_bound(v.begin(),v.end(),x);
v.insert(P,x);
}
}s[];
//pos:id->position
//id:
int main()
{
// freopen("data.in","r",stdin);
// freopen("my.out","w",stdout);
n=read();int T=read();
len=pow(1.0*n,0.618);
num=(n-)/len;
for(int i=;i<n;i++){
s[i/len].add(read());
}
while(T--){
int p=read();
int numl=,numr=,posl=,posr=;
if(==p){
int ans=;
int l=read(),r=read(),c=read();
l--,r--;
numl=l/len,numr=r/len;
posl=l%len,posr=r%len;
if(numl!=numr){
for(int i=numl+;i<numr;i++){
ans+=upper_bound(s[i].v.begin(),s[i].v.end(),c)-lower_bound(s[i].v.begin(),s[i].v.end(),c);
}
for(int i=posl;i<=s[numl].L;i++){
if(s[numl].a[i]==c){
ans++;
}
}
for(int i=;i<=posr;i++){
if(s[numr].a[i]==c){
ans++;
}
}
}
else{
for(int i=posl;i<=posr;i++){
if(s[numl].a[i]==c){
ans++;
}
}
}
printf("%d\n",ans);
}
else{
int l=read()-,r=l+;
numl=l/len,numr=r/len;
posl=l%len,posr=r%len;
int lc=s[numl].a[posl],rc=s[numr].a[posr];
if(lc==rc){
continue;
}
vector<int>::iterator it;
it=lower_bound(s[numl].v.begin(),s[numl].v.end(),lc);
s[numl].v.erase(it);
it=lower_bound(s[numl].v.begin(),s[numl].v.end(),rc);
s[numl].v.insert(it,rc);
it=lower_bound(s[numr].v.begin(),s[numr].v.end(),rc);
s[numr].v.erase(it);
it=lower_bound(s[numr].v.begin(),s[numr].v.end(),lc);
s[numr].v.insert(it,lc);
swap(s[numl].a[posl],s[numr].a[posr]);
// for(int i=0;i<=num;i++){
// for(int j=0;j<s[i].v.size();j++){
// printf("%d ",s[i].v[j]);
// }
// printf("\n");
// }
// printf("\n");
}
}
return ;
}
分桶
其实直接记录下每个数字出现的位置放到vector里面然后二分一下就可以了，
思路很简单，正如管理员说的“很多人学数据结构学傻了”，简单的问题不需要那么麻烦的
不过这题有个小坑，编号指的就是从左向右数第几个，不是兔子的属性
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#include<vector>
#define MAXN 300005
using namespace std;
int n;
vector<int> s[MAXN];
int read(){
int x=;char ch=getchar();
while(ch<''||ch>''){ch=getchar();}
while(ch>=''&&ch<=''){x=(x<<)+(x<<)+(ch^);ch=getchar();}
return x;
}
void write(int x){
if(!x){
putchar();
putchar('\n');
return;
}
char t[]={};
int cnt=;
while(x){
t[++cnt]=x%;
x/=;
}
for(int i=cnt;i>=;i--){
putchar(+t[i]);
}
putchar('\n');
}
int a[MAXN];
int main()
{
// freopen("color2.in","r",stdin);
n=read();
int T=read();
for(int i=;i<=n;i++){
a[i]=read();
s[a[i]].push_back(i);
}
while(T--){
int p=read();
if(p==){
int l=read(),r=read(),c=read();
write(upper_bound(s[c].begin(),s[c].end(),r)-lower_bound(s[c].begin(),s[c].end(),l));
}
else{
int l=read(),r=l+;
if(a[l]==a[r]){
continue;
}
int P1=lower_bound(s[a[l]].begin(),s[a[l]].end(),l)-s[a[l]].begin();
int P2=lower_bound(s[a[r]].begin(),s[a[r]].end(),r)-s[a[r]].begin();
s[a[l]][P1]=r;
s[a[r]][P2]=l;
swap(a[l],a[r]);
}
}
return ;
}
AC
有点卡常
总的来说这题出的还算不错的，很灵活的数据结构