以下總結參考了許多大佬們的博客，開篇先（大佬）%

莫隊的入門題目主要為莫隊和帶修莫隊在，這里就先在這里總結一下這兩類題目的一些屬性。

我認為莫隊本質是一種比較優化的暴力查找法。在通過分塊操作后把復雜度降低。這個降低的復雜度的大小主要和你分塊的方法有著巨大的關系。

普通的莫隊，n個元素m個區間詢問，他的最佳分塊大小為? n/√m? ?，如果默認n==m的話? 復雜度會降到 O(n*√n)? 即可以完美運行5X10e5數據。

帶修的莫隊，多加了一個讓指針移動的因子—時間 t? ，時間復雜度比較難求，如果設定n，m，t相等的情況下?復雜度O（nlogn+n^5/3）,同樣可以運行50000數據。

貼兩道經典的莫隊存板子。

P1494 [國家集訓隊]小Z的襪子?https://www.luogu.org/problemnew/show/P1494

#include<bits/stdc++.h> using namespace std; #define ll long long ll b,ans=0;int l=1,r=0; ll gcd(ll a,ll b) {if(b==0) return a;else return gcd(b,a%b); } struct dd {int x,y,num; }a[50050]; ll cmp(dd x,dd y) {if(x.x/b==y.x/b) return x.y<y.y;else return x.x<y.x; } ll bj[50050]={0}; ll c[50050]; pair<int,int> pr[50050]; void solve(int x,int add) {ans-=bj[c[x]]*bj[c[x]];//cout<<ans<<endl;bj[c[x]]+=add;ans+=bj[c[x]]*bj[c[x]];//cout<<ans<<endl; } int main() {ll n,m,q,i,j;scanf("%lld%lld",&n,&q);b=sqrt(n);for(i=1;i<=n;i++) scanf("%lld",&c[i]);for(i=1;i<=q;i++) scanf("%d%d",&a[i].x,&a[i].y),a[i].num=i;sort(a+1,a+q+1,cmp);for(i=1;i<=q;i++){ll lon=a[i].y-a[i].x+1;//cout<<a[i].x<<" "<<a[i].y<<"lon="<<lon<<endl;while(l<a[i].x){solve(l,-1);l++;}while(l>a[i].x){solve(l-1,1);l--;}while(r<a[i].y){solve(r+1,1);r++;}while(r>a[i].y){solve(r,-1);r--;}//cout<<l<<" "<<r<<endl;int aans=ans-lon;lon=lon*(lon-1);int gc=gcd(aans,lon);//cout<<ans<<" "<<lon<<endl;if(aans==0) pr[a[i].num].first=0,pr[a[i].num].second=1;else pr[a[i].num].first=aans/gc,pr[a[i].num].second=lon/gc;}for(i=1;i<=q;i++) printf("%d/%d\n",pr[i].first,pr[i].second); }

P1903 [國家集訓隊]數顏色 / 維護隊列?https://www.luogu.org/problemnew/show/P1903

#include<bits/stdc++.h> using namespace std; int ans=0;int l=1,r=0,t=0; int b; struct dd {int x,y,t,num; }a[50050]; struct dt {int p, v; }tw[50050]; int cmp(dd x,dd y) {if(x.x/b==y.x/b){if(x.y/b==y.y/b) return x.t<y.t;return x.y/b<y.y/b;} else return x.x<y.x; } int bj[1000050]={0}; int e=0,tim=0; int c[50050]; int pr[50050]; void solve(int x,int add) {bj[c[x]]+=add;if(bj[c[x]]==0&&add==-1) ans--;if(bj[c[x]]==1&&add==1) ans++;//cout<<ans<<endl; } void time_change(int i,int tt) {if(tw[tt].p>=a[i].x&&tw[tt].p<=a[i].y) {bj[c[tw[tt].p]]--;if(bj[c[tw[tt].p]]==0) ans--;bj[tw[tt].v]++;if(bj[tw[tt].v]==1) ans++;}swap(tw[tt].v,c[tw[tt].p]); } int main() {int n,q,i;char qq[5];scanf("%d%d",&n,&q);b=pow(n,0.66666);for(i=1;i<=n;i++) scanf("%d",&c[i]);for(i=1;i<=q;i++) {scanf("%s",qq);if(qq[0]=='Q'){e++;scanf("%d%d",&a[e].x,&a[e].y);a[e].t=tim;a[e].num=e;}else{tim++;scanf("%d%d",&tw[tim].p,&tw[tim].v);}}sort(a+1,a+e+1,cmp);for(i=1;i<=e;i++){//cout<<a[i].x<<" "<<a[i].y<<"lon="<<lon<<endl;while(l<a[i].x){solve(l,-1);l++;}while(l>a[i].x){solve(l-1,1);l--;}while(r<a[i].y){solve(r+1,1);r++;}while(r>a[i].y){solve(r,-1);r--;}//cout<<l<<" "<<r<<endl;while(t<a[i].t){time_change(i,t+1);t++;}while(t>a[i].t){time_change(i,t);t--;}//cout<<ans<<" "<<lon<<endl;pr[a[i].num]=ans;}for(i=1;i<=e;i++) printf("%d\n",pr[i]); }

?

轉載于:https://www.cnblogs.com/wsblm/p/10813007.html

總結

以上是生活随笔為你收集整理的莫队+带修莫队模板与总结的全部內容，希望文章能夠幫你解決所遇到的問題。

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