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
|
using namespace std; inline bool (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() { 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("%dn", q[i].ret); } } return 0; }
|
近期评论