【概述】

普通莫隊由于強制離線是不能修改的，但對于強制在線的題，可以在普通莫隊的基礎上強行加上一維時間軸 time，表示這次操作的時間，即在每個詢問前已經完成了多少次修改。

簡單來說，就是將詢問 [l,r]，變為 [l,r,time]，那么指針也可在時間維度上移動，使得第一關鍵字是左端點所在的塊，第二關鍵字是右端點所在的塊，第三關鍵字是時間，即 [l,r,time] 多了一維可移動的方向：

• [l-1,r,time]
• [l+1,r,time]
• [l,r-1,time]
• [l,r+1,time]
• [l,r,time-1]
• [l,r,time+1]

int l=1,r=0,time=0; for(int i=1;i<=m;++i){int ql=q[i].l,qr=q[i].r;//詢問的左右端點int qtime=q[i].time;//詢問的時間軸while(l>ql) add(--l);//[l-1,r,time]while(l<ql) del(l++);//[l+1,r,time]while(r<qr) add(++r);//[l,r+1,time]while(r>qr) del(r--);//[l,r-1,time]while(time<qtime) change(i,++time);//[l,r,time+1]while(time>qtime) change(i,time--);//[l,r,time-1]res[q[i].id]=ans;//獲取答案 }

暴力查詢時，如果當前修改數比詢問的修改數少就把沒修改的進行修改，反之回退，需要注意的是，修改分為兩部分：

• 若修改的位置在當前區間：更新答案
• 無論修改的位置是否在當前區間：都要進行修改，以供 add 和 del 函數在以后更新答案

struct Change{int pos;//要修改的位置int col;//要改成的值 }c[N]; void add(int x){...}//統計新的，根據具體情況修改 void del(int x){...}//減去舊的，根據具體情況修改 void change(int x,int ti){//改變時間軸if(c[ti].pos>=q[x].l&&c[ti].pos<=q[x].r){del(a[c[ti].pos]);//刪除指定位置上的值add(c[ti].col);//統計新的數}swap(c[ti].col,a[c[ti].pos]);//直接互換，下次執行時必定是回退這次操作 } /*change函數會執行或回退修改ti,執行還是回退取決于是否執行過，x表明當前的詢問是x，即若修改了區間[q[x].l,q[x].r],便要更新答案 */

【排序】

由于第一關鍵字是左端點所在的塊，第二關鍵字是右端點所在的塊，第三關鍵字是時間，雖然多了一個維度，但轉移仍是 O(1) 的復雜度，只需要在排序時考慮 time 的影響即可。

• 當左右端點在同一個塊中：以 time 為關鍵字排序
• 當左端點在同一個塊中，右端點不在：以右端點為關鍵字排序
• 當左端點不在同一個塊：以左端點為關鍵字排序

bool cmp(Node a,Node b){//排序if( (a.l/block)==(b.l/block) ){//當左端點位于同一個塊時if( (a.r/block)==(b.r/block) )//當右端點位于同一個塊時return a.time<b.time;elsereturn a.r<b.r;}else//當左端點不位于同一個塊時return a.l<b.l;//return (a.l/block)^(b.l/block) ? a.l<b.l : ( ((a.r/block)^(b.r/block))?a.r<b.r:a.time<b.time ); }

【分塊與時間復雜度】

設 block?為分塊大小，c 為修改個數，q 為詢問個數，l、r 塊表示以 l/block、r/block?分的塊，每個 l 塊包含 n/block 個 r 塊

• 對于時間指針 time，每個 r 塊最多會移動 c 次，共有??個 r 塊，總移動次數為?
• 對于左端點指針 l：l 塊內最多移動 block 次，換 l 塊時最多移動 2*block 次，總移動次數為：
• 對于右端點指針 r：總移動次數為：
  • r 塊內最多移動 block 次，換 r 塊時最多移動 2*block 次，所有 l 塊內移動次數之和為?
  • 換 l 塊時最多移動 n 次，總的換 l 塊時移動次數之和為?

故總移動次數為：，因而總時間復雜度為?

由于一般題目不會分別告訴修改與詢問的個數，統一用 m 表示，則有：

通過 Mathermatica 軟件分析，要想讓總時間復雜度最小，可以得到 block 的取值如下：

由于式子過于復雜，難以寫出帶修莫隊的最佳分塊數，因此一般視作 n=m，即有：

令總時間復雜度最小，可得到當??時最小，此時總時間復雜度為：

綜上，分塊一般以??為一塊，分成? 個塊，總時間復雜度為：

int block=pow(n,0.66666);

?【模版】

struct Node{int l,r;//詢問的左右端點int time;//時間維度int id;//詢問的編號 }q[N]; struct Change{int pos;//要修改的位置int col;//要改成的值 }c[N]; int n,m,a[N]; int block;//分塊 int numQ,numC;//查詢、修改操作的次數 LL ans,cnt[N]; LL res[N];bool cmp(Node a,Node b){//排序return (a.l/block)^(b.l/block) ? a.l<b.l : ((a.r/block)^(b.r/block)?a.r<b.r:a.time<b.time); }void add(int x){//統計新的，根據具體情況修改if(cnt[x]==0)ans++;cnt[x]++;} void del(int x){//減去舊的，根據具體情況修改cnt[x]--;if(cnt[x]==0)ans--; } void change(int x,int ti){//改變時間軸if(c[ti].pos>=q[x].l&&c[ti].pos<=q[x].r){del(a[c[ti].pos]);//刪除指定位置上的值add(c[ti].col);//統計新的數}swap(c[ti].col,a[c[ti].pos]);//直接互換，下次執行時必定是回退這次操作 } int main(){while(scanf("%d%d",&n,&m)!=EOF){ans=0;numQ=0;numC=0;memset(cnt,0,sizeof(cnt));block=pow(n,0.66666);//分塊for(int i=1;i<=n;i++)scanf("%d",&a[i]);for(int i=1;i<=m;i++){char op[10];scanf("%s",op);if(op[0]=='Q'){//查詢操作++numQ;//查詢操作次數+1scanf("%d%d",&q[numQ].l,&q[numQ].r);q[numQ].id=numQ;//序號q[numQ].time=numC;//時間軸}else{//修改操作++numC;//修改操作次數+1scanf("%d%d",&c[numC].pos,&c[numC].col);}}sort(q+1,q+numQ+1,cmp);//對詢問進行排序int l=1,r=0,time=0;//左右指針與時間軸for(int i=1;i<=numQ;i++){int ql=q[i].l,qr=q[i].r;//詢問的左右端點int qtime=q[i].time;//詢問的時間軸while(l>ql) add(a[--l]);//[l-1,r,time]while(l<ql) del(a[l++]);//[l+1,r,time]while(r<qr) add(a[++r]);//[l,r+1,time]while(r>qr) del(a[r--]);//[l,r-1,time]while(time<qtime) change(i,++time);//[l,r,time+1]while(time>qtime) change(i,time--);//[l,r,time-1]res[q[i].id]=ans;//獲取答案}for(int i=1;i<=numQ;i++)printf("%lld\n",res[i]);}return 0; }

?

總結

以上是生活随笔為你收集整理的分治 —— 莫队算法 —— 带修莫队的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。