65 分分块代码。

评测记录

#include<bits/stdc++.h>
using namespace std;
int n,q,p[300010],k,ans;//p[]原始数组
int d[300010],m,e[555];//m块长 d[]每个节点所属块 e[]每块起点 
int op,l,r,x;//操作 
short f[405][300010];
int main(){
	scanf("%d%d",&n,&q);
	m=750;//读入 & 分块初始化 
	for(int i=1;i<=n;i++){
		int u=(i+m-1)/m;
		d[i]=u;
		if(e[u]==0) e[u]=i;
	}
	for(int i=1;i<=n;i++){
		scanf("%d",&p[i]);
		f[d[i]][p[i]]++;
	}
	while(q--){
		scanf("%d",&op);
		if(op==2){//修改操作 
			scanf("%d",&x);
			if(d[x]!=d[x+1]){// x 和 x+1 位于不同块时改变两个块中该数个数 
				f[d[x]][p[x]]--;
				f[d[x]][p[x+1]]++;
				f[d[x+1]][p[x]]++;
				f[d[x+1]][p[x+1]]--;
			}
			swap(p[x],p[x+1]);//换位 
		}
		else{//查询操作 
			scanf("%d%d%d",&l,&r,&x);
			ans=0;
			for(int i=l;i<=r;){
				int u=d[i];
				if(e[u+1]<=r&&e[u+1]>0&&(d[i]!=d[i-1]||i==1)){//跳一整个块 
					ans+=f[u][x];
					i=e[u+1];
				}
				else{//跳一个点 
					if(p[i]==x) ans++;
					i++;
				}
			}
			printf("%d\n",ans);
		}
	}
}