# 一无所|知的小|J f

### 题解 P3939 【数颜色】

posted on 2018-12-28 22:02:27 | under 题解 |

emm...这题分块有点卡空间

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#define maxn 300010
#define re register
#define FOR(i, l, r) for(re int i = l; i <= r; ++i)
using namespace std;

int n, m, c, r, t, x, y, s;
int sq;
int a[maxn], b[maxn], z[maxn];
bool bl[maxn];
int cnt[550][maxn];
inline void in(re int &x){
x=0;re int bl = 1;char c=getchar();
while(c<'0'||c>'9'){
if(c == '-')
bl = -1;
c=getchar();
}
while(c<='9'&&c>='0'){
x=(x<<1)+(x<<3)+(c^'0');
c=getchar();
}
x *= bl;
}

void out(re int a){
if(a < 0) {
putchar('-');
a = -a;
}
if(a>=10)out(a/10);
putchar(a%10+'0');
}

inline int query(int x, int y, int k) {
int res = 0;
FOR(i, x, min(y, b[x]*sq))
if(a[i] == k)
++res;
if(b[x] != b[y])
FOR(i, (b[y]-1)*sq+1, y)
if(a[i] == k)
++res;
if(b[x] < b[y]) {
res += (cnt[b[y]-1][k]-cnt[b[x]][k]);
}
return res;
}

void change(int x) {
if(b[x] == b[x+1]) {
swap(a[x], a[x+1]);
}
else {
--cnt[b[x]][a[x]];
++cnt[b[x]][a[x+1]];
swap(a[x], a[x+1]);
}
}

int main() {
in(n), in(m);
sq = min(n, 1528);
FOR(i, 1, n)
in(a[i]), b[i] = (i-1)/sq+1, z[i] = a[i], bl[a[i]] = 1;
z[0] = n;
sort(z+1, z+z[0]+1);
z[0] = unique(z+1, z+z[0]+1)-z-1;
FOR(i, 1, n) {
a[i] = lower_bound(z+1, z+z[0]+1, a[i])-z;
++cnt[b[i]][a[i]];
}
FOR(i, 2, b[n]) {
FOR(j, 1, z[0])
cnt[i][j] += cnt[i-1][j];
}
FOR(i, 1, m) {
in(t);
if(t == 1) {
in(x), in(y), in(s);
if(!bl[s]) {
puts("0");
continue;
}
s = lower_bound(z+1, z+z[0]+1, s)-z;
out(query(x, y, s)),
putchar(10);
}
else {
in(x);
change(x);
}
}
}