[ZJ b417][莫隊] 區間眾數

原題連結
莫隊算法(Mo's algorithm)這幾年非常的紅啊～～
有很多需要複雜資料結構(LCT , 樹鏈剖分 , 持久化資料結構....) 的題目都可以用莫隊搭配樹壓平之類的技巧作到帶根號的複雜度。

回到題目。區間眾數，這是一道經典的莫隊題。
網路上關於莫隊算法的教程非常豐富，我只簡單說一下過程：

1. 維護curL,curR兩個指針代表當前所維護的區間左界和右界，當要處理下一個詢問時，我們邊將左右界移動到該次詢問的左右界，邊處理進來當前維護區間的元素和出去當前維護區間的元素；處理進來和出去的元素這件事情應該可以快速完成(O(1) or O(lgn) )

2. 當curL和curR成功移動到目前詢問的左右界，我們應該可以快速獲得該次詢問的答案(O(1) or O(lgn))。

3. 莫隊算法的精華所在：該如何安排詢問順序使得curL和curR的移動次數不會太多次？
運用分塊思想，假設將序列切成K塊，對於詢問左界在同一塊的詢問放在一起，右界則遞增排序。
這樣做的話時間會是怎麼樣呢？
先分析左界移動次數：在同一塊的詢問中，每次curL移動到詢問左界的移動次數不會超過(N/K)次(該塊的大小就只有N/K)，不同塊的左界移動最多總共也只有N次，所以左界移動的時間複雜度為O(Q*N/K)
而同一塊中的右界因為是遞增的，移動次數最多N次，對於不同塊因為最多也只有K塊，每次最多花費O(N)，那麼總體時間就是O(K*N)。
取K=sqrt(N)，我們有了一個時間複雜度O(Q*sqrt(N) + N*sqrt(N))的作法！

#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=100000+5;
const int maxm=1000000+5;
struct Query
{
    int ql,qr,id,bid;
    bool operator < (const Query& rhs) const {return bid<rhs.bid || (bid==rhs.bid && qr<rhs.qr);}
}qu[maxm];
int show[maxn],cnt[maxn],ans,a[maxn],n,m,Anscnt[maxm],Ansshow[maxm];
void add(int x)
{
    cnt[x]++;
    show[cnt[x]]++;
    show[cnt[x]-1]--;
    if(show[cnt[x]]==1) ans=max(ans,cnt[x]);
}
void sub(int x)
{
    cnt[x]--;
    show[cnt[x]]++;
    show[cnt[x]+1]--;
    if(show[cnt[x]+1]==0 && ans==cnt[x]+1) ans=cnt[x];
}
void Mo()
{
    sort(qu,qu+m);
    show[0]=n;
    for(int i=1;i<=n;i++) cnt[i]=0;
    for(int i=0,L=0,R=-1;i<m;i++)
    {
        while(R<qu[i].qr) {R++;add(a[R]);}
        while(R>qu[i].qr) {sub(a[R]);R--;}
        while(L<qu[i].ql) {sub(a[L]);L++;}
        while(L>qu[i].ql) {L--;add(a[L]);}
        Anscnt[qu[i].id]=ans;Ansshow[qu[i].id]=show[ans];
    }
    for(int i=0;i<m;i++) printf("%d %d\n",Anscnt[i],Ansshow[i]);
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=0;i<n;i++) scanf("%d",a+i);
    int K=sqrt(n);
    for(int i=0;i<m;i++)
    {
        scanf("%d%d",&qu[i].ql,&qu[i].qr);qu[i].ql--,qu[i].qr--;
        qu[i].id=i;
        qu[i].bid=(qu[i].ql)/K;
    }
    Mo();
}