luogu P3709 大爷的字符串题

二次联通门 : luogu P3709 大爷的字符串题

/*

    luogu P3709 大爷的字符串题

    莫队

    看了半天题目 + 题解

    才弄懂了要求什么。。。

    维护两个数组

    一个记录数字i出现了几次

    一个记录出现了i次的有几个数。。

*/

#include <algorithm>

#include <cstdlib>

#include <cstdio>

#include <cmath>

#define Max 200090

void read (int &now)

{

    now = ;

    register char word = getchar ();

    while (word < '' || word > '')

        word = getchar ();

    while (word >= '' && word <= '')

    {

        now = now *  + word - '';

        word = getchar ();

    }

}

int belong[Max];

struct Query_Data

{

    int l, r;

    int Id;

    bool operator < (const Query_Data &now) const

    {

        if (belong[this->l] == belong[now.l])

            return this->r < now.r;

        return belong[this->l] < belong[now.l];

    }

};

int number[Max];

int N, M;

int count[Max];

int Answer[Max], Result;

Query_Data query[Max];

int __rank[Max];

int __count[Max];

inline void Updata (int now, bool type)

{

    if (type)

    {

        if (count[number[now]] == Result)

            Result ++;

        __count[count[number[now]]] --;

        ++ count[number[now]];

        __count[count[number[now]]] ++;

    }

    else

    {

        if (count[number[now]] == Result && __count[count[number[now]]] == )

            Result --;

        __count[count[number[now]]] --;

        count[number[now]] --;

        ++ __count[count[number[now]]];

    }

}

int main (int argc, char *argv[])

{

    read (N);

    read (M);

    int K_Size = sqrt (N);

    for (int i = ; i <= N; i ++)

    {

        read (number[i]);

        __rank[i] = number[i];

        belong[i] = (i + ) / K_Size;

    }

    std :: sort (__rank + , __rank +  + N);

    int Size = std :: unique (__rank + , __rank +  + N) - __rank - ;

    for (int i = ; i <= N; i ++)

        number[i] = std :: lower_bound (__rank + , __rank +  + Size, number[i]) - __rank;

    for (int i = ; i <= M; i ++)

    {

        read (query[i].l);

        read (query[i].r);

        query[i].Id = i;

    }

    std :: sort (query + , query +  + M);

    int l = , r = ;

    for (int i = ; i <= M; i ++)

    {

        while (l < query[i].l)

            Updata (l ++, false);

        while (l > query[i].l)

            Updata (-- l, true);

        while (r < query[i].r)

            Updata (++ r, true);

        while (r > query[i].r)

            Updata (r --, false);

        Answer[query[i].Id] = Result;

    }

    for (int i = ; i <= M; i ++)

        printf ("%d\n", -Answer[i]);

    //system ("pause");

    return ;

}