今天兔哥講了一波莫隊(duì)，比較有趣，先加一個鏈接,這是她的教程

rabbithu.cnblogs.com

這里就不詳細(xì)說了，其實(shí)就是兩個指針來優(yōu)化的暴力。一開始排序函數(shù)有問題，沒用上莫隊(duì)的核心思想：把查詢區(qū)間先排序，第一關(guān)鍵字是左指針?biāo)诘膮^(qū)間（注意，不是大小），第二關(guān)鍵字是右指針的大小。

然后一點(diǎn)點(diǎn)模擬就行了，左指針向前就減，否則加。

這里有一道板子題

題目描述HH 有一串由各種漂亮的貝殼組成的項(xiàng)鏈。HH 相信不同的貝殼會帶來好運(yùn)，所以每次散步完后，他都會隨意取出一段貝殼，思考它們所表達(dá)的含義。HH 不斷地收集新的貝殼，因此，他的項(xiàng)鏈變得越來越長。有一天，他突然提出了一個問題：某一段貝殼中，包含了多少種不同的貝殼？這個問題很難回答……因?yàn)轫?xiàng)鏈實(shí)在是太長了。于是，他只好求助睿智的你，來解決這個問題。 輸入輸出格式 輸入格式：第一行：一個整數(shù)N，表示項(xiàng)鏈的長度。第二行：N 個整數(shù)，表示依次表示項(xiàng)鏈中貝殼的編號（編號為0 到1000000 之間的整數(shù)）。第三行：一個整數(shù)M，表示HH 詢問的個數(shù)。接下來M 行：每行兩個整數(shù)，L 和R（1 ≤ L ≤ R ≤ N），表示詢問的區(qū)間。輸出格式：M 行，每行一個整數(shù)，依次表示詢問對應(yīng)的答案。

直接貼代碼（數(shù)據(jù)加強(qiáng)之后AC不了，但貌似所有的算法都AC不了？）

#include<cstdio> #include<algorithm> #include<iostream> #include<cmath> using namespace std; typedef long long ll; ll que[500010],n,m,bk; struct node{int ans;int l,r; }; node k[200010]; int pl = 1,pr = 0; bool cmp(node a,node b) {if(a.l / bk != b.l / bk){return a.l < b.l;}else{return a.r < b.r;} } ll cnt[200010],num = 0; void add(int a) {if(!cnt[a])num++;cnt[a]++; } void del(int a) {cnt[a]--;if(!cnt[a])num--; } ll ans[200010]; int main() {cin>>n;bk = ceil(sqrt(n));for(int i = 1;i <= n;i++){scanf("%lld",&que[i]);}cin>>m;for(int i = 1;i <= m;i++){scanf("%d%d",&k[i].l,&k[i].r);k[i].ans = i;}sort(k + 1,k + m + 1,cmp);for(int i = 1;i <= m;i++){while(pl < k[i].l)del(que[pl++]);while(pl > k[i].l)add(que[--pl]);while(pr > k[i].r)del(que[pr--]);while(pr < k[i].r)add(que[++pr]);ans[k[i].ans] = num;}for(int i = 1;i <= m;i++){printf("%lld\n",ans[i]);}return 0; }

還有一個題，是莫隊(duì)的來源，好像莫隊(duì)是隊(duì)長從這一題的論文答辯發(fā)明的。

題目描述作為一個生活散漫的人，小Z每天早上都要耗費(fèi)很久從一堆五顏六色的襪子中找出一雙來穿。終于有一天，小Z再也無法忍受這惱人的找襪子過程，于是他決定聽天由命……具體來說，小Z把這N只襪子從1到N編號，然后從編號L到R(L 盡管小Z并不在意兩只襪子是不是完整的一雙，甚至不在意兩只襪子是否一左一右，他卻很在意襪子的顏色，畢竟穿兩只不同色的襪子會很尷尬。你的任務(wù)便是告訴小Z，他有多大的概率抽到兩只顏色相同的襪子。當(dāng)然，小Z希望這個概率盡量高，所以他可能會詢問多個(L,R)以方便自己選擇。然而數(shù)據(jù)中有L=R的情況，請?zhí)嘏羞@種情況，輸出0/1。 輸入輸出格式 輸入格式：輸入文件第一行包含兩個正整數(shù)N和M。N為襪子的數(shù)量，M為小Z所提的詢問的數(shù)量。接下來一行包含N個正整數(shù)Ci，其中Ci表示第i只襪子的顏色，相同的顏色用相同的數(shù)字表示。再接下來M行，每行兩個正整數(shù)L，R表示一個詢問。輸出格式：包含M行，對于每個詢問在一行中輸出分?jǐn)?shù)A/B表示從該詢問的區(qū)間[L,R]中隨機(jī)抽出兩只襪子顏色相同的概率。若該概率為0則輸出0/1，否則輸出的A/B必須為最簡分?jǐn)?shù)。（詳見樣例）輸入輸出樣例 輸入樣例#1： 復(fù)制6 4 1 2 3 3 3 2 2 6 1 3 3 5 1 6輸出樣例#1： 復(fù)制2/5 0/1 1/1 4/15

?這個是計數(shù)，但是本質(zhì)上沒什么區(qū)別，上代碼

#include<cstdio> #include<algorithm> #include<iostream> #include<cmath> using namespace std; typedef long long ll; ll que[50010],bk,n,m; struct node{int ans;int l,r; }; node k[50010]; ll pl = 1,pr = 0; ll ava[50010],bvb[50010]; bool cmp(node a,node b) {if(a.l / bk == b.l / bk){return a.r < b.r;}else{return a.l < b.l;} } ll gcd(ll a,ll b) {ll p;while(a % b != 0){p = a % b;a = b;b = p;}return b; } ll cnt[50010],num = 0; void add(int a) {num -= cnt[a] * cnt[a];cnt[a]++;num += cnt[a] * cnt[a]; } void del(int a) {num -= cnt[a] * cnt[a];cnt[a]--;num += cnt[a] * cnt[a]; } ll ans[50010],aa,bb,cc; int main() {cin>>n>>m;for(int i = 1;i <= n;i++){scanf("%lld",&que[i]);}bk = ceil(sqrt(n));for(int i = 1;i <= m;i++){scanf("%d%d",&k[i].l,&k[i].r);k[i].ans = i;}sort(k + 1,k + m + 1,cmp);for(int i = 1;i <= m;i++){if(k[i].l == k[i].r){ava[k[i].ans] = 0;bvb[k[i].ans] = 1;continue;}while(pl < k[i].l)del(que[pl++]);while(pl > k[i].l)add(que[--pl]);while(pr > k[i].r)del(que[pr--]);while(pr < k[i].r)add(que[++pr]);pl = k[i].l;aa = num + k[i].l - k[i].r - 1;bb = (ll)(k[i].r - k[i].l + 1) * (k[i].r - k[i].l);cc = gcd(aa,bb);aa /= cc;bb /= cc;ava[k[i].ans] = aa;bvb[k[i].ans] = bb; // cout<<aa<<"/"<<cc<<endl; }for(int i = 1;i <= m;i++){printf("%lld/%lld\n",ava[i],bvb[i]);}return 0; }

但是莫隊(duì)的修改好像復(fù)雜度不是很優(yōu)秀，而且不能在線只能離線處理，所以我又學(xué)了一個其他的結(jié)構(gòu)：分塊

再附上一個鏈接，講的超級好：

http://hzwer.com/8053.html

其實(shí)這種東西和線段樹區(qū)別不大，但是線段樹好像復(fù)雜度更好？

然后去鋼了一道黑題，做的懷疑人生，最后抄代碼過的

題目背景親愛的哥哥：你在那個城市里面過得好嗎？我在家里面最近很開心呢。昨天晚上奶奶給我講了那個叫「絕望」的大壞蛋的故事的說！它把人們的房子和田地搞壞，還有好多小朋友也被它殺掉了。我覺得把那么可怕的怪物召喚出來的那個壞蛋也很壞呢。不過奶奶說他是很難受的時候才做出這樣的事的……最近村子里長出了一大片一大片的蒲公英。一刮風(fēng)，這些蒲公英就能飄到好遠(yuǎn)的地方了呢。我覺得要是它們能飄到那個城市里面，讓哥哥看看就好了呢！哥哥你要快點(diǎn)回來哦！愛你的妹妹 VioletAzure 讀完這封信之后微笑了一下?！捌压帷?題目描述在鄉(xiāng)下的小路旁種著許多蒲公英，而我們的問題正是與這些蒲公英有關(guān)。為了簡化起見，我們把所有的蒲公英看成一個長度為n的序列 (a1,a2..an)(a_1,a_2..a_n)(a1?,a2?..an?) ，其中 aia_iai? 為一個正整數(shù)，表示第i棵蒲公英的種類編號。而每次詢問一個區(qū)間 [l,r]，你需要回答區(qū)間里出現(xiàn)次數(shù)最多的是哪種蒲公英，如果有若干種蒲公英出現(xiàn)次數(shù)相同，則輸出種類編號最小的那個。注意，你的算法必須是在線的 輸入輸出格式 輸入格式：第一行兩個整數(shù) n,m ，表示有n株蒲公英，m 次詢問。接下來一行n個空格分隔的整數(shù) aia_iai? ，表示蒲公英的種類再接下來m 行每行兩個整數(shù) l0,r0l_0,r_0l0?,r0? ，我們令上次詢問的結(jié)果為 x（如果這是第一次詢問， 則 x=0）。令 l=(l0+x?1)modn+1,r=(r0+x?1)modn+1l=(l_0+x-1)\bmod n + 1,r=(r_0+x-1) \bmod n + 1l=(l0?+x?1)modn+1,r=(r0?+x?1)modn+1 ，如果 l>r，則交換 l,r 。最終的詢問區(qū)間為[l,r]。輸出格式：輸出m 行。每行一個整數(shù)，表示每次詢問的結(jié)果。

這個題的思路不算難，就是離散化+分塊處理在線找眾數(shù)，但是代碼真是狗

#include<iostream> #include<cstdio> #include<map> #include<vector> #include<algorithm> #include<cstring> using namespace std; typedef long long ll; int n,m,blo,id; int v[500005],bl[500005]; int f[1005][1005]; //f[i][j]表示i~j的眾數(shù)是多少 map<int,int>mp; int val[500005],cnt[500005]; vector<int>ve[500005]; void pre(int x) { memset(cnt,0,sizeof(cnt));int mx = 0,ans = 0;for(int i=(x - 1) * blo + 1;i <= n;i++){ cnt[v[i]]++;int t = bl[i];if(cnt[v[i]] > mx || (cnt[v[i]] == mx && val[v[i]] < val[ans])) //找x~t真正的眾數(shù) ans = v[i],mx = cnt[v[i]];f[x][t] = ans;} } int query(int l,int r,int x) {int t = upper_bound(ve[x].begin(),ve[x].end(),r) - lower_bound(ve[x].begin(),ve[x].end(),l);return t; } int query(int a,int b) {int ans,mx;ans = f[bl[a] + 1][bl[b] - 1];mx = query(a,b,ans); //整區(qū)間里的眾數(shù) for(int i = 1;i <= min(blo * bl[a],b);i++){int t = query(a,b,v[i]);if(t > mx || (t == mx && val[v[i]] < val[ans])){ans = v[i];mx = t;}}if(bl[a] != bl[b]){for(int i = (bl[b] - 1) * blo + 1;i <= b;i++){int t = query(a,b,v[i]);if(t > mx || (t == mx && val[v[i]] < val[ans]))ans = v[i],mx = t;}}return ans; } int main() {scanf("%d%d",&n,&m);blo = 200;int ans = 0;for(int i = 1;i <= n;i++){scanf("%d",&v[i]);if(!mp[v[i]]){mp[v[i]] = ++id; //離散化 val[id] = v[i]; //第一次出現(xiàn)的位置 }v[i] = mp[v[i]];ve[v[i]].push_back(i);}for(int i = 1;i <= n;i++) //處理i在第幾個塊bl[i] = (i - 1) / blo + 1;for(int i = 1;i <= bl[n];i++) //預(yù)處理f數(shù)組 pre(i);for(int i = 1;i <= m;i++){int a,b;scanf("%d%d",&a,&b);a = (a + ans - 1) % n + 1;b = (b + ans - 1) % n + 1;if(a > b)swap(a,b);ans = val[query(a,b)];printf("%d\n",ans);}return 0; }

大家加油！！！

轉(zhuǎn)載于:https://www.cnblogs.com/DukeLv/p/9160738.html

總結(jié)

以上是生活随笔為你收集整理的莫队分块的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。