BZOJ 1878: [SDOI2009]HH的项链

1878: [SDOI2009]HH的项链

Time Limit: 4 Sec Memory Limit: 64 MB
Submit: 3548 Solved: 1757
[Submit][Status][Discuss]

Description

HH有一串由各种漂亮的贝壳组成的项链。HH相信不同的贝壳会带来好运，所以每次散步完后，他都会随意取出一段贝壳，思考它们所表达的含义。HH不断地收集新的贝壳，因此，他的项链变得越来越长。有一天，他突然提出了一个问题：某一段贝壳中，包含了多少种不同的贝壳？这个问题很难回答。。。因为项链实在是太长了。于是，他只好求助睿智的你，来解决这个问题。

Input

第一行：一个整数N，表示项链的长度。第二行：N个整数，表示依次表示项链中贝壳的编号（编号为0到1000000之间的整数）。第三行：一个整数M，表示HH询问的个数。接下来M行：每行两个整数，L和R（1 ≤ L ≤ R ≤ N），表示询问的区间。

Output

M行，每行一个整数，依次表示询问对应的答案。

Sample Input

6
1 2 3 4 3 5
3
1 2
3 5
2 6

Sample Output

2
2
4

HINT

对于20%的数据，N ≤ 100，M ≤ 1000；
对于40%的数据，N ≤ 3000，M ≤ 200000；
对于100%的数据，N ≤ 50000，M ≤ 200000。

Source

Day2

[Submit][Status][Discuss]

OTZ NEIGHTHORN

树状数组O(NlogN) 或莫队算法O(N^1.5)

 #include <bits/stdc++.h>

 /* SCANNER */

 #define siz 1024

 inline int get_c(void)

 {

     static char buf[siz];

     static char *head = buf + siz;

     static char *tail = buf + siz;

     if (head == tail)

         fread(head = buf, , siz, stdin);

     return *head++;

 }

 inline int get_i(void)

 {

     register int ret = ;

     register int neg = false;

     register int bit = get_c();

     for (; bit < ; bit = get_c())

         if (bit == '-')neg ^= true;

     for (; bit > ; bit = get_c())

         ret = ret *  + bit - ;

     return neg ? -ret : ret;

 }

 #define N 50005

 #define M 200005

 #define V 1000005

 int n, m;

 int num[N];

 /* PREWORK */

 int nxt[N];

 int lst[V];

 int fst[V];

 /* QUERY */

 int lt[M];

 int rt[M];

 int ans[M];

 int ord[M];

 inline bool cmp(int a, int b)

 {

     return lt[a] < lt[b];

 }

 /* B I T */

 int tree[N];

 inline void add(int p, int k)

 {

     for (; p <= n; p += p&-p)

         tree[p] += k;

 }

 inline int ask(int p)

 {

     int ret = ;

     for (; p >= ; p -= p&-p)

         ret += tree[p];

     return ret;

 }

 /* MAIN */

 signed main(void)

 {

     n = get_i();

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

         num[i] = get_i();

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

         lst[i] = n + ;

     for (int i = n; i >= ; --i)

         nxt[i] = lst[num[i]], lst[num[i]] = i;

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

         if (!fst[num[i]])

         {

             add(i, );

             fst[num[i]] = ;

         }

     m = get_i();

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

     {

         ord[i] = i;

         lt[i] = get_i();

         rt[i] = get_i();

     }

     std::sort(ord + , ord +  + m, cmp);

     int left = ;

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

     {

         while (left < lt[ord[i]])

         {

             add(left, -);

             add(nxt[left], );

             ++left;

         }

         ans[ord[i]] = ask(rt[ord[i]]);

     }

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

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

 }

@Author: YouSiki

秒客网