数据结构学傻了……
对每个颜色开一个vector，记录该颜色出现过的位置
查询操作直接在vector里二分查找(l,r)，一减就可以
修改操作直接二分后swap就可以了
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#define LL long long
using namespace std;
LL read() {
LL k = 0, f = 1; char c = getchar();
while(c < '0' || c > '9') {
if(c == '-') f = -1;
c = getchar();
}
while(c >= '0' && c <= '9')
k = k * 10 + c - 48, c = getchar();
return k * f;
}
vector <int> col[300010];
int a[300010];
int main() {
int n = read(), q = read();
for(int i = 1; i <= n; ++i)
a[i] = read(), col[a[i]].push_back(i);
while(q--) {
int opt = read();
if(opt == 1) {
int l = read(), r = read(), c = read();
int x = lower_bound(col[c].begin(), col[c].end(), l) - col[c].begin() - 1;
int y = upper_bound(col[c].begin(), col[c].end(), r) - col[c].begin() - 1;
if(y-x < 0) printf("0
");
else printf("%d
", y-x);
}
else {
int pos = read();
if(a[pos] == a[pos+1]) continue;
int x = lower_bound(col[a[pos]].begin(), col[a[pos]].end(), pos) - col[a[pos]].begin();
int y = lower_bound(col[a[pos+1]].begin(), col[a[pos+1]].end(), pos+1) - col[a[pos+1]].begin();
swap(col[a[pos]][x], col[a[pos+1]][y]); swap(a[pos], a[pos+1]);
}
}
return 0;
}