https://www.luogu.com.cn/problem/P3939

 const int N = 1000010;
#define mid  ((l+r)>>1)
int n, m, a[N], last[N];
int root[N], idx;
int ls[N * 40], rs[N * 40], sum[N * 40];

void change(int& u, int l, int r, int p, int k)
{
    if (!u) u = ++idx;
    sum[u] += k;
    if (l == r) return;
    if (p <= mid) change(ls[u], l, mid, p, k);
    else change(rs[u], mid + 1, r, p, k);
}
int find(int u, int l, int r,int x,int y)
{
    if (x <= l && r <= y) return sum[u];
    int ans = 0;
    if (x <= mid) ans += find(ls[u], l, mid, x, y);
    if (y > mid) ans += find(rs[u], mid + 1, r, x, y);
    return ans;
}

void solve()
{

    cin >> n >> m;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        change(root[a[i]], 1, n, i, 1);
    }

    while (m--)
    {
        int c;
        cin >> c;
        if (c == 2)
        {
            int x;
            cin >> x;
            change(root[a[x]], 1, n, x, -1);
            change(root[a[x + 1]], 1, n, x + 1, -1);
            change(root[a[x]], 1, n, x + 1, 1);
            change(root[a[x + 1]], 1, n, x, 1);
            swap(a[x], a[x + 1]);
        }
        else
        {
            int l, r, x;
            cin >> l >> r >> x;
            cout << find(root[x], 1, n, l, r) << '\n';
        }
    }
}