2018牛客多校01 J Different Integers

发表于 | 更新于 | 分类于 ， | 评论数： | 阅读次数：

链接：https://www.nowcoder.com/acm/contest/139/J

n个数，q次查询l,r。求[1,l]和[r,n]中不同数的个数。

这题首先开二倍数组，然后在后n个位置重新存一遍这n个数，这样就相当于查询[r, n+l]内不同数的个数，用莫队或者bit离线计数都能做（代码是莫队）。 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#include <bits/stdc++.h>
using namespace std;
 
inline bool scan_d(int &num) {
    char in;bool IsN=false;
    in=getchar();
    if(in==EOF) return false;
    while(in!='-'&&(in<'0'||in>'9')) in=getchar();
    if(in=='-'){ IsN=true;num=0;}
    else num=in-'0';
    while(in=getchar(),in>='0'&&in<='9'){
        num*=10,num+=in-'0';
    }
    if(IsN) num=-num;
    return true;
}
 
const int maxn = 100100;
using Query = struct { int l, r, ret, id; };
int n, m;
int a[maxn<<1], be[maxn<<1], L, R;
Query q[maxn];
int vis[maxn], sz;
 
inline void add(int x, int &ret) {
    vis[x]++;
    if(vis[x] == 1) ret++;
}
 
inline void remove(int x, int &ret) {
    vis[x]--;
    if(vis[x] == 0) ret--;
}
 
signed main() {
    // freopen("in", "r", stdin);
    while(~scanf("%d%d",&n,&m)) {
        sz = static_cast<int>(sqrt(n));
        memset(vis, 0, sizeof(vis));
        for(int i = 1; i <= n; i++) {
            scan_d(a[i]);
            a[n+i] = a[i];
            be[i] = static_cast<int>(i / sz);
            be[i+n] = static_cast<int>((i + n) / sz);
        }
        for(int i = 1; i <= m; i++) {
            scan_d(q[i].r); scan_d(q[i].l);
            q[i].r += n;
            q[i].id = i;
        }
        sort(q+1, q+m+1, [](Query a, Query b) {
            return be[a.l] == be[b.l] ? a.r < b.r : a.l < b.l;
        });
        int ret = 0;
        L = 1, R = 0;
        for(int i = 1; i <= m; i++) {
            while(L < q[i].l) { remove(a[L], ret); L++; }
            while(L > q[i].l) { L--; add(a[L], ret); }
            while(R < q[i].r) { R++; add(a[R], ret); }
            while(R > q[i].r) { remove(a[R], ret); R--; }
            q[i].ret = ret;
        }
        sort(q+1, q+m+1, [](Query a, Query b){
            return a.id < b.id;
        });
        for(int i = 1; i <= m; i++) {
            printf("%d\n", q[i].ret);
        }
    }
    return 0;
}