引入小例
zl 姐姐有一串數，由于學生化太頭禿了，所以現在他想問你 m(m≤1e5) 次，其中L到R區間出現次數在3次及以上的數有多少個？
解決方案
線段樹
效率低下，不好維護，
故引入莫隊——一種處理區間問題的離線演算法，
莫隊
0.演算法名字的由來
莫隊演算法，其中的“莫”指國家隊莫濤巨佬，CCCCOrz，
1.基本原理
莫隊是優美的暴力，
先讓我們回到開頭來幫幫 zl 姐姐，
Continue 是個傻子，所以他打了個暴力；
for(int i=l;i<=r;i++)
{
cnt[a[i]]++;
if(cnt[a[i]]>=3)
ans++;
}
如果每次詢問都這么打的話，很明顯， O(nm) 的演算法是會讓 zl 姐姐難堪的，（zl 姐姐：你來真的？）
聰明的你撿起了傻子 Continue 打的暴力，覺得好不容易打的，扔了多可惜啊，
于是你開始對剛剛的暴力結果進行改造，
你想，既然我們已經知道了 [L,R] 的結果，那么 [L-1,R]，[L+1,R]，[L,R-1]，[L,R+1]的結果不就可以也一起很容易得到了嗎？
在 O(1) 的時間里，現在你的手里現在已經有了 5 個答案，
這是多好的事，于是你將這個性質推廣到了所有的詢問，
詳細的，為了方便，我們不妨將推廣得來的四個答案一類稱作推廣區間，將推廣區間們對應的原區間 [L,R] 稱作原區間，只要我們知道了原區間的答案，那么要求的推廣區間便也就可求了，
所以現在問題就轉化為了：“如何使詢問區間成為一個推廣區間”，進一步地，由于我們無法改變詢問，這個問題變成了“如何使推廣區間匹配上詢問區間”，
顯然，我們可以通過不斷修改原區間的方式，來匹配與詢問區間一致的推廣區間，
很明顯，這種不斷變化范圍的操作，我們可以通過 while 回圈實作，
可是如果每次都 while ，我們的代碼仍然是一份傻子代碼——會 T 得慘不忍睹（g2020 lvt && dlz大佬語）
所以接下來才是真正應用時的莫隊：分塊+sort，
2.基本莫隊
有了上面的一些推論，現在你意識到，每次詢問時都要根據查詢區間的大小調整原區間大小，且由于詢問區間并不相同（否則該問題將沒有意義），所以這個操作是必然的，
在必然的情況下，我們要盡可能的使該操作盡量的快，由此才能做到優美的暴力，
再次分析上面的程序，我們發現該操作的主要時耗來源于鎖定所需區間的程序，所以我們應盡可能的將每次需要的推廣區間之間的差減小，以此來減少變化區間范圍的次數，提高了效率，
而達到此目的的唯一方式就是對查詢區間進行排序，
這便是優美莫隊里面的sort部分，
至于排序的標準，自然要依靠于分塊啦~
由于我們要求兩個區間盡量的相似，所以應滿足單調性，
其原因如圖，
注：紫色曲線代表每次鎖定區間時需移動的長度，
圖一是未排序的效果，可以看見陰影的部分我們是重復移動了的，這樣十分浪費時間，
只要排序成圖二這樣，要移動的區間就再也不會重疊啦~
確定了排序的任務，那么排序的關鍵字呢？
答案是分塊，
分塊合理地將節點劃分了不同的區間，這樣就可以較快的比較，
我們通過左端點所處的塊進行排序，若處于同一個塊則比較右端點，這樣就可以科學有效的降低時間啦~
3.代碼
上面的都懂了，接下來就是一份普通莫隊的模板代碼，一般的題都可以變著花樣套板子，（當然不能算帶權莫隊樹上莫隊）
Problem:HH的項鏈
這道題luogu是卡了莫隊的（但還是有神仙巨佬卡過去了），在這里只是作為練手題，A6個點，T4個點就差不多了，主要是思想，思想！
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;
const int maxn=2e6+10;
const int inf=1<<30;
inline int Read()
{
int s=0;
int f=1;
char ch=getchar();
while(ch<'0'||ch>'9')
{
if(ch=='-')
f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9')
{
s=(s<<1)+(s<<3)+ch-'0';
ch=getchar();
}
return s*f;
}
int n,m;
struct Num
{
int l,r; //詢問的區間
int num; //詢問的答案
int id; //詢問的次序
}a[maxn];
int temp[maxn];
int bel[maxn]; //belong
bool cmp(Num x,Num y)
{
return ((bel[x.l]==bel[y.l]) && (x.r<y.r)) || (bel[x.l]<bel[y.l]);
}
bool cmp2(Num x,Num y)
{
return x.id<y.id;
}
int cnt[maxn]; //記錄次數的陣列
int top;
int ans; //答案有幾個
inline void Add(int x)
{
cnt[x]++;
if(cnt[x]==1)
ans++;
}
inline void Dele(int x)
{
cnt[x]--;
if(!cnt[x])
ans--;
}
int main()
{
n=Read();
int k=sqrt(n); //分塊
for(int i=1;i<=n;i++)
{
temp[i]=Read();
bel[i]=(i-1)/k+1;
}
m=Read();
for(int i=1;i<=m;i++)
{
int x,y;
x=Read();
y=Read();
if(x>y)
swap(x,y);
a[i].l=x;
a[i].r=y;
a[i].id=i;
}
sort(a+1,a+m+1,cmp);
int l=1,r=0;
for(int i=1;i<=m;i++)
{
int x=a[i].l;
int y=a[i].r;
//鎖定區間的程序
while(l>x)
Add(temp[l-1]),--l;
while(l<x)
Dele(temp[l]),++l;
while(r<y)
Add(temp[r+1]),++r;
while(r>y)
Dele(temp[r]),--r;
a[i].num=ans;
}
sort(a+1,a+m+1,cmp2); //離線演算法按原序輸出答案
for(int i=1;i<=m;i++)
printf("%d\n",a[i].num);
return 0;
}
感謝閱讀！
可愛的 zl 小姐姐感謝了你，終于，你們都有了光明的未來……！
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/263626.html
標籤：C++
上一篇：配置 OpenGL(Win10 + VS2019 + GLAD + GLFW) 并創建自己的第一個 OpenGL 專案