帶修改的莫隊算法

【前言】

普通的莫隊算法固然強大，但是不能支援修改操作

于是就有了帶修改莫隊這種神奇的東西。

【做法】

普通的莫隊可以看這裡

那麼對于詢問的結構體，可以多記錄一個資訊ti

表示到這個詢問為止最後做的修改的編号

至于排序麼……與普通莫隊類似，隻是把ti作為第3個關鍵字

（當R在同一塊的，就按ti排序）

處理時，要使目前區間，修改的指針一起動

（每次線性移動修改指針（修改/撤銷），使得前ti個修改操作恰好被執行）

這樣就完美解決了~~

【複雜度】

值得注意的是，帶修改莫隊的分塊要分成 N13 ，每塊 N23

下面證明帶修改莫隊的複雜度

L指針：無論如何，對于每次詢問，L最多移動 N23 次，共Q次詢問就是O(Q N23 )

R指針：這裡就比較複雜了，需要分情況讨論：

由于R是在每個L塊上又分了 N13 塊，可以這樣考慮

1. 如果相鄰兩次詢問使R沒有跨越任何塊，則最多走 N23 次，即O(Q N23 )
2. 跨越了R塊，但處于同一L塊，則最多走 N23 次，因為共有 N13∗N13=N23 塊，是以總複雜度為O( N43 )
3. 跨越了L塊，則最多走n次，即O( N43 )

現在看t指針（修改操作）的移動：

1. 沒有跨越任何塊，每次N步，總複雜度O( N53 )

2. 跨越了R塊，但處于同一L塊，還是一樣，總複雜度O( N53 )

3. 跨越了L塊，也是一樣的，隻是L的塊數是 N13 ，那麼就是O( N43 )

是以說，如果N和Q是同一個級别的，複雜度就是O( N53 )級别的

這對于一個暴力來說已經很好了，大家可以在各大比賽中放心使用

【例題】

BZOJ2120

裸題……題解在這裡

#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
const int maxn=,maxs=;
int n,q,h[maxn],a[maxn],b[maxn],hsh[maxs],topQ,topC,ans[maxn];
struct ask{
    int l,r,ti,id;
    bool operator<(const ask&b)const{
        if (h[l]==h[b.l]){
            if (h[r]==h[b.r]) return ti<b.ti;
            return r<b.r;
        }
        return l<b.l;
    }
}que[maxn];
struct cha{
    int bf,af,i;
}Ch[maxn];
inline int red(){
    int tot=,f=;char ch=getchar();
    while (ch<'0'||'9'<ch) {if (ch=='-') f=-f;ch=getchar();}
    while ('0'<=ch&&ch<='9') tot=tot*+ch-,ch=getchar();
    return tot*f;
}
inline char fstchar(){
    char ch=getchar();
    while (ch<'A'||'Z'<ch) ch=getchar();
    return ch;
}
void blocker(){
    int k=pow(n,/);
    for (int i=;i<=n;i++) h[i]=(i-)/k+;
}
int now=;
void update(int x,int d){
    if (d==){
        if (hsh[a[x]]==) now++;
        hsh[a[x]]++;
    }else{
        if (hsh[a[x]]==) now--;
        hsh[a[x]]--;
    }
}
void change(int x,int w,int l,int r){
    if (l<=x&&x<=r) update(x,-),a[x]=w,update(x,);
     else a[x]=w;
}
int main(){
    n=red(),q=red();
    blocker();
    for (int i=;i<=n;i++) a[i]=b[i]=red();
    for (int i=;i<=q;i++)
     if (fstchar()=='Q'){
        que[++topQ].l=red(),que[topQ].r=red();
        que[topQ].id=topQ;que[topQ].ti=topC;
     }else{
        int x=red(),y=red();
        Ch[++topC].bf=b[x];Ch[topC].af=y;
        b[x]=y;Ch[topC].i=x;
     }
    sort(que+,que++topQ);
    update(,);change(Ch[].i,Ch[].af,,);
    for (int i=,L=,R=,t=;i<=topQ;i++){
        while (t<que[i].ti) t++,change(Ch[t].i,Ch[t].af,L,R);
        while (t>que[i].ti) change(Ch[t].i,Ch[t].bf,L,R),t--;
        while (L<que[i].l) update(L++,-);
        while (L>que[i].l) update(--L,);
        while (R<que[i].r) update(++R,);
        while (R>que[i].r) update(R--,-);
        ans[que[i].id]=now;
    }
    for (int i=;i<=topQ;i++) printf("%d\n",ans[i]);
    return ;
}