[COCI2016-2017#5] Poklon

题目描述

给定一个包含 $N$ 个自然数的数组。

接着需要回答 $Q$ 次询问，每次询问输出区间 $[L,R]$ 内恰好出现两次的自然数的数量。

输入格式

第一行，两个整数 $N,Q$，分别表示数组元素数量和询问次数。

第二行，$N$ 个整数，表示数组中的元素。

接下来的 $Q$ 行，每行两个整数 $L,R$，表示询问的区间。

输出格式

共 $Q$ 行，依次对应每次询问的结果。

样例 #1

样例输入 #1

5 1
1 2 1 1 1
1 3

样例输出 #1

1

样例 #2

样例输入 #2

5 2
1 1 1 1 1
2 4
2 3

样例输出 #2

0
1

样例 #3

样例输入 #3

5 2
1 1 2 2 3
1 1
1 5

样例输出 #3

0
2

提示

【样例 1 解释】

区间 $[1,3]$ 中只有 $1$ 恰好出现了两次。

【数据规模与约定】

对于 $40\%$ 的数据，$N,Q \le 5000$。

对于 $100\%$ 的数据，$1 \le N,Q \le 5 \times 10^5$，$1 \le L \le R \le N$，数组中的元素都是小于 $10^9$ 的自然数。

【提示与说明】

题目译自 COCI 2016-2017 CONTEST #5 T5 Poklon。

本题分值按 COCI 原题设置，满分 $140$。

看到这个题，本来以为要用树状数组，非常麻烦啊
但是，当我看到了时间限制

5.00s(克罗地亚人是不会树状数组吗)

于是，莫队启动！！！

直接暴切蓝水题

Round 1

看了一眼数据范围，值域那么大，个数那么小，离散化于是

#include <cstdio>
#include <cctype>
#include <algorithm>
#include <unordered_map>
#include <cmath>

char *p1, *p2, buf[100000];
#define nc() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1 ++ )

using namespace std;

const int N = 500000 + 10, M = N;

int n, m, res = 0, k = 1;
int a[N], pos[N], cnt[N];
int ans[M];
unordered_map<int, int> mp;

struct Q
{
    int l, r, k;

    bool operator <(const Q &t)const
    {
        return pos[l] == pos[t.l] ? r < t.r : pos[l] < pos[t.l];
    }
}q[M];

inline void Add(register int x)
{
    if (cnt[mp[a[x]]] == 1)
        res ++ ;
    if (cnt[mp[a[x]]] == 2)
        res -- ;
    cnt[mp[a[x]]] ++ ;
}

inline void Sub(register int x)
{
    if (cnt[mp[a[x]]] == 3)
        res ++ ;
    if (cnt[mp[a[x]]] == 2)
        res -- ;
    cnt[mp[a[x]]] -- ;
}

template<typename T> inline void read(register T &qwq)
{
    register T x = 0, f = 1;
    register char ch = nc();
    while (!isdigit(ch))
    {
        if (ch == '-')
            f = -1;
        ch = nc();
    }
    while (isdigit(ch))
        x = (x << 1) + (x << 3) + (ch ^ 48), ch = nc();
    qwq = x * f;
    return;
}

template<typename T> inline void write(register T x)
{
    if (x < 0)
        putchar('-'), x = -x;
    if (x > 9)
        write(x / 10);
    putchar(x % 10 + '0');
    return;
}

int main()
{
    read(n), read(m);

    register int siz = sqrt(n);
    for (register int i = 1; i <= n; i ++ )
    {
        read(a[i]);
        pos[i] = i / siz;
        if (mp.find(a[i]) == mp.end())
            mp[a[i]] = k ++ ;
    }

    for (register int i = 1; i <= m; i ++ )
        read(q[i].l), read(q[i].r), q[i].k = i;

    sort(q + 1, q + 1 + m);

    register int l = 1, r = 0;
    for (register int i = 1; i <= m; i ++ )
    {
        while (l > q[i].l) Add(-- l);
        while (r < q[i].r) Add(++ r);
        while (l < q[i].l) Sub(l ++ );
        while (r > q[i].r) Sub(r -- );

        ans[q[i].k] = res;
    }

    for (register int i = 1; i <= m; i ++ )
        write(ans[i]), puts("");

    return 0;
}

然鹅好像TLE了,话说unordeed_map的复杂度有点玄学？

Round 2

#include <cstdio>
#include <cctype>
#include <algorithm>
#include <cmath>

char *p1, *p2, buf[100000];
#define nc() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1 ++ )

using namespace std;

const int N = 500000 + 10, M = N;

int n, m, res = 0, k = 1;
int a[N], c[N], pos[N], cnt[N];
int ans[M];

struct Q
{
    int l, r, k;

    bool operator <(const Q &t)const
    {
        return pos[l] == pos[t.l] ? r < t.r : pos[l] < pos[t.l];
    }
}q[M];

inline void Add(register int x)
{
    if (cnt[a[x]] == 1)
        res ++ ;
    if (cnt[a[x]] == 2)
        res -- ;
    cnt[a[x]] ++ ;
}

inline void Sub(register int x)
{
    if (cnt[a[x]] == 3)
        res ++ ;
    if (cnt[a[x]] == 2)
        res -- ;
    cnt[a[x]] -- ;
}

template<typename T> inline void read(register T &qwq)
{
    register T x = 0, f = 1;
    register char ch = nc();
    while (!isdigit(ch))
    {
        if (ch == '-')
            f = -1;
        ch = nc();
    }
    while (isdigit(ch))
        x = (x << 1) + (x << 3) + (ch ^ 48), ch = nc();
    qwq = x * f;
    return;
}

template<typename T> inline void write(register T x)
{
    if (x < 0)
        putchar('-'), x = -x;
    if (x > 9)
        write(x / 10);
    putchar(x % 10 + '0');
    return;
}

int main()
{
    read(n), read(m);
    register int len = n;

    register int siz = n / (sqrt(m * 2 / 3));
    for (register int i = 1; i <= n; i ++ )
    {
        read(a[i]);
        pos[i] = i / siz;
        c[i] = a[i];
    }

    for (register int i = 1; i <= m; i ++ )
        read(q[i].l), read(q[i].r), q[i].k = i;

    sort(c + 1, c + 1 + len);
    len = unique(c + 1, c + 1 + len) - c - 1;
    for (register int i = 1; i <= n; i ++ )
        a[i] = lower_bound(c + 1, c + 1 + len, a[i]) - c;

    sort(q + 1, q + 1 + m);

    register int l = 1, r = 0;
    for (register int i = 1; i <= m; i ++ )
    {
        while (l > q[i].l) Add(-- l);
        while (r < q[i].r) Add(++ r);
        while (l < q[i].l) Sub(l ++ );
        while (r > q[i].r) Sub(r -- );

        ans[q[i].k] = res;
    }

    for (register int i = 1; i <= m; i ++ )
        write(ans[i]), puts("");

    return 0;
}

换了一种方式，成功AC

Round 3

#include <cstdio>
#include <cctype>
#include <algorithm>
#include <unordered_map>
#include <cmath>

char *p1, *p2, buf[100000];
#define nc() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1 ++ )

using namespace std;

const int N = 500000 + 10, M = N;

int n, m, res = 0, k = 1;
int a[N], pos[N], cnt[N];
int ans[M];
unordered_map<int, int> mp;

struct Q
{
    int l, r, k;

    bool operator <(const Q &t)const
    {
        return pos[l] == pos[t.l] ? r < t.r : pos[l] < pos[t.l];
    }
}q[M];

inline void Add(register int x)
{
    if (cnt[a[x]] == 1)
        res ++ ;
    if (cnt[a[x]] == 2)
        res -- ;
    cnt[a[x]] ++ ;
}

inline void Sub(register int x)
{
    if (cnt[a[x]] == 3)
        res ++ ;
    if (cnt[a[x]] == 2)
        res -- ;
    cnt[a[x]] -- ;
}

template<typename T> inline void read(register T &qwq)
{
    register T x = 0, f = 1;
    register char ch = nc();
    while (!isdigit(ch))
    {
        if (ch == '-')
            f = -1;
        ch = nc();
    }
    while (isdigit(ch))
        x = (x << 1) + (x << 3) + (ch ^ 48), ch = nc();
    qwq = x * f;
    return;
}

template<typename T> inline void write(register T x)
{
    if (x < 0)
        putchar('-'), x = -x;
    if (x > 9)
        write(x / 10);
    putchar(x % 10 + '0');
    return;
}

int main()
{
    read(n), read(m);

    register int siz = n / (sqrt(m * 2 / 3));
    for (register int i = 1; i <= n; i ++ )
    {
        read(a[i]);
        pos[i] = i / siz;
            //mp[a[i]] = k ++ ;
    }

    for (register int i = 1; i <= m; i ++ )
        read(q[i].l), read(q[i].r), q[i].k = i;

    sort(q + 1, q + 1 + m);

    register int l = 1, r = 0;
    for (register int i = 1; i <= m; i ++ )
    {
        while (l > q[i].l) Add(-- l);
        while (r < q[i].r) Add(++ r);
        while (l < q[i].l) Sub(l ++ );
        while (r > q[i].r) Sub(r -- );

        ans[q[i].k] = res;
    }

    for (register int i = 1; i <= m; i ++ )
        write(ans[i]), puts("");

    return 0;
}

真幽默啊，这题真假，居然不用离散化就过了

简直了(你被骗了)

完结，撒花