【莫队算法】(COCI 2016/2017 round 5) Poklon

太过爱你忘了你带给我的痛 2021-12-03 12:09 249阅读 0赞

### 文章目录 ###

*  题目
 *   *  题目描述
     *  输入格式
     *  输出格式
     *  样例
     *   *  样例输入1
         *  样例输出1
         *  样例输入2
         *  样例输出2
         *  样例输入3
         *  样例输出3
     *  数据范围与提示
 *  解析
 *  Code

--------------------

# 题目 #

## 题目描述 ##

M i r k o Mirko Mirko是一个非常简单的人。 M i r k o Mirko Mirko的朋友 D a r k o Darko Darko给了他由 N N N个自然数组成的一个数组，并问了他 Q Q Q个问题。每个问题由两个整数 L L L和 R R R组成，要求 M i r k o Mirko Mirko回答在数组的第 L L L位到第 R R R位中恰好出现两次的不同值有多少种。

## 输入格式 ##

第一行输入包含整数 N N N和 Q Q Q（ 1 ≤ N 1≤N 1≤N， Q ≤ 5 ∗ 1 e 5 Q≤5\*1e5 Q≤5∗1e5）。表示数组中自然数的个数和问题的个数。 第二行输入包含 N N N个自然数 a i ai ai（ a i ≤ 1 e 9 ai≤1e9 ai≤1e9）。表示数组。 接下来Q行每行包含两个整数 L i Li Li和 R i Ri Ri（ 1 ≤ L i ≤ R i ≤ N 1≤Li≤Ri≤N 1≤Li≤Ri≤N），表示一个问题询问的区间。

## 输出格式 ##

输出 Q Q Q行，每行一个整数。第i行的整数表示第i个问题的答案。

## 样例 ##

### 样例输入1 ###

5 1
    1 2 1 1 1
    1 3

### 样例输出1 ###

### 样例输入2 ###

5 2
    1 1 1 1 1
    2 4
    2 3

### 样例输出2 ###

0
    1

### 样例输入3 ###

5 2
    1 1 2 2 3
    1 1
    1 5

### 样例输出3 ###

0
    2

## 数据范围与提示 ##

对于 40 % 40\\% 40%的数据， N ≤ 5000 N≤5000 N≤5000且 Q ≤ 5000 Q≤5000 Q≤5000。

# 解析 #

这道题其实一看有 n n n， m m m，还有 l , r l, r l,r的区间查询，基本上可以看出是莫队算法的板子了，当然如果有人不知道莫队算法的，可以[看看][Link 1]。

但是这里还有一个小坑点，如果说要用 c n t cnt cnt数组来存每个数出现的次数的话显然要炸——“ a i ≤ 1 e 9 ai≤1e9 ai≤1e9”。因此我们需要将每个数离散化后再来存到 c n t cnt cnt数组中。

当然离散化可以用 S T L STL STL也可以用数组来存，这里我就只贴数组的了主要是忘记 m a p map map怎么搞了QwQ

但是不知道为什么，有些用 m a p map map做的竟然 T T T了，这就很震惊了，再次庆幸还好我只会数组离散化。。。

最后还有一点十分关键，**排序记着要分块啊** **排序记着要分块啊** **排序记着要分块啊** 某位dalao就是因为忘记这个东西，导致 T L E TLE TLE，惋惜&庆幸

# Code #

#include <cstdio>
    #include <cmath>
    #include <cstdlib>
    #include <algorithm>
    #include <vector>
    #include <set>
    #include <map>
    #include <string>
    #include <queue>
    #include <stack>
    #include <cstring>
    #include <iostream>
    using namespace std;
    #define reg register
    #define LL long long
    #define INF 0x3f3f3f3f
    
    template<typename T>
    void re (T &x){ 
        x = 0;
        int f = 1;
        char c = getchar ();
        while (c < '0' || c > '9'){ 
            if (c == '-') f = -1;
            c = getchar ();
        }
        while (c >= '0' && c <= '9'){ 
            x = (x << 1) + (x << 3) + c - 48;
            c = getchar ();
        }
        x *= f;
    }
    
    template<typename T>
    void pr (T x){ 
        if (x < 0){ 
            putchar ('-');
            x = ~x + 1;
        }
        if (x / 10) pr (x / 10);
        putchar (x % 10 + 48);
    }
    
    const int N = 5e5;
    
    int n, q, siz, a[N + 5], sum, curL = 1, curR, cnt[N + 5];
    LL ans, Ans[N + 5];
    struct node{ 
        int l, r, id;
        bool operator < (const node &rhs) const{ 
            return (l / siz == rhs.l / siz) ? r < rhs.r : l < rhs.l;
        }
    }que[N + 5];
    struct num{ 
        int x, id;
        bool operator < (const num &rhs) const{ 
            return x < rhs.x;
        }
    }b[N + 5];
    
    void add (int x){ 
        if (cnt[x] == 2) ans --;
        cnt[x] ++;
        if (cnt[x] == 2) ans ++;
    }
    
    void remov (int x){ 
        if (cnt[x] == 2) ans --;
        cnt[x] --;
        if (cnt[x] == 2) ans ++;
    }
    
    int main (){ 
        re (n); re (q);
        siz = sqrt (n);
        for (int i = 1; i <= n; i++){ 
            re (a[i]);
            b[i].x = a[i];
            b[i].id = i;
        }
        sort (b + 1, b + 1 + n);
        for (int i = 1; i <= n; i++){ 
            if (b[i].x != b[i - 1].x)
                sum ++;
            a[b[i].id] = sum;
        }
        for (int i = 1; i <= q; i++){ 
            re (que[i].l); re (que[i].r);
            que[i].id = i;
        }
        sort (que + 1, que + 1 + q);
        for (int i = 1; i <= q; i++){ 
            while (curL < que[i].l)
                remov (a[curL ++]);
            while (curL > que[i].l)
                add (a[--curL]);
            while (curR < que[i].r)
                add (a[++curR]);
            while (curR > que[i].r)
                remov (a[curR--]);
            Ans[que[i].id] = ans;
        }
        for (int i = 1; i <= q; i++){ 
            pr (Ans[i]);
            putchar (10);
        }
        return 0;
    }

[Link 1]: https://blog.csdn.net/weixin_43925239/article/details/96361460