O(n2S+mS)O(\frac {n^2} {S} + mS)

S=nmS = \frac {n}{\sqrt{m}}时 复杂度最小 即 O(nm)O(n\sqrt{m})

带修改莫队

BZOJ 2122

https://www.lydsy.com/JudgeOnline/problem.php?id=2120

题意:给定nn个数 mm个询问
两种操作:
1、Q L R 计算[L, R]区间不同种类个数
2、R L R 将a[L]改为R

莫队带修改
不带修改的莫队维护的是[L,R][L, R]这段区间。 那么带修改的话,维护的就是[L,R,t][L, R, t]这个状态,那么同样的按莫队的思路维护即可。排序的话如果右边界相等的话取按tt排序。 注意时间修改要放在区间修改完成之后再进行。

时间复杂度证明如下:

摘自Oi wiki
左右端点所在块不变,时间在排序后单调向右移,这样的复杂度是 O(n)O(n)

若左右端点所在块改变,时间一次最多会移动 n 个格子,时间复杂度 O(n)O(n)

左端点所在块一共有n13n^{\frac{1}{3}} 中,右端点也是n13n^{\frac{1}{3}} 种,一共 种n13×n13n^{\frac{1}{3}} \times n^{\frac{1}{3}},每种乘上移动的复杂度O(n)O(n) ,总复杂度 O(n53)O(n^{\frac {5} {3}})

#include <bits/stdc++.h>
#define pa pair<int, int>
#define mp make_pair
#define lowbit(x) ((x)&(-x))
#define mem(i, a) memset(i, a, sizeof(i))
#define sqr(x) ((x)*(x))
#define ls (k << 1)
#define rs (k << 1 | 1)
using namespace std;
typedef long long ll;
template <typename T>
inline void read(T &X) {
    X = 0; char ch = 0; T op = 1;
    for(; ch > '9' || ch < '0'; ch = getchar())
        if(ch == '-') op = -1;
    for(; ch >= '0' && ch <= '9'; ch = getchar())
        X = (X << 3) + (X << 1) + ch - 48;
    X *= op;
}

const int INF = 0x3f3f3f3f;
const int N = 10005 + 5;
int len;
struct query {
    int l,r,id,t;
    bool operator <(const query &a) const {
        if(l / len == a.l / len) {
            if(r == a.r) return t < a.t;
            return r < a.r;
        }
        return l < a.l;
    }
}q[N];
int a[N],c[N],ans[N];
int upd[N][3];
int n,m,c1,c2,sum,vis[1000055];
inline void add(int x) {
    if(vis[a[x]] == 0) sum++;
    vis[a[x]]++;
}
inline void del(int x) {
    vis[a[x]]--;
    if(vis[a[x]] == 0) sum--;
}
inline void solve(int ti, int i) {
    if(q[i].l <= upd[ti][0] && upd[ti][0] <= q[i].r) {
        if(--vis[a[upd[ti][0]]] == 0) sum--;
        if(++vis[upd[ti][1]] == 1) sum++;
    }swap(a[upd[ti][0]], upd[ti][1]);
}
int main() {
#ifdef INCTRY
    freopen("input.txt", "rt", stdin);
#endif
    read(n); read(m);
    len = pow(n, (double) 2 / (double) 3);
    for(int i = 1; i <= n; i++) {
        read(a[i]); c[i] = a[i];
    }

    for(int i = 1; i <= m; i++) {
        char ch; cin >> ch;
        int l,r; read(l); read(r);
        if(ch == 'Q') {
            q[++c1] = {l, r, c1}; q[c1].t = c2;
        } else {
            upd[++c2][0] = l; upd[c2][1] = r;
        }
    }
    sort(q + 1, q + c1 + 1);
    int l = 1, r = 0, now = 0;
    for(int i = 1; i <= c1; i++) {
        while(l < q[i].l) del(l++);
        while(l > q[i].l) add(--l);
        while(r < q[i].r) add(++r);
        while(r > q[i].r) del(r--);
        while(now < q[i].t) solve(++now, i);
        while(now > q[i].t) solve(now--, i);
        ans[q[i].id] = sum;
    }
    for(int i = 1; i <= c1; i++) {
        cout << ans[i] << "\n";
    }


#ifdef INCTRY
    cerr << "\nTime elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
#endif
    return 0;
}