LightOJ 1188 Fast Queries（简单莫队）

阅读量：5302 次

发布时间：2019-06-14

本文共 1837 字，大约阅读时间需要 6 分钟。

1188 - Fast Queries

Time Limit: 3 second(s)

Memory Limit: 64 MB

Given an array of N integers indexed from 1 to N, and q queries, each in the form i j, you have to find the number of distinct integers from index i to j (inclusive).

Input

Input starts with an integer T (≤ 5), denoting the number of test cases.

The first line of a case is a blank line. The next line contains two integers N (1 ≤ N ≤ 10⁵), q (1 ≤ q ≤ 50000). The next line contains N space separated integers forming the array. There integers range in [0, 10⁵].

Each of the next q lines will contain a query which is in the form i j (1 ≤ i ≤ j ≤ N).

Output

For each test case, print the case number in a single line. Then for each query you have to print a line containing number of distinct integers from index i to j.

Sample Input

Output for Sample Input

8 5

1 1 1 2 3 5 1 2

1 8

2 3

3 6

4 5

4 8

Case 1:

Note

Dataset is huge. Use faster I/O methods.

题目链接：

莫队大法好，看到n的范围是1e5也就直接上莫队了，用vis记录数字出现次数，显然对于区间的增减进行更新vis，若缩小区间导致vis[val]为0则说明少了一个数，反之为1则就是增加一个数，700MS还可以，另外一种不同的做法是用树状数组更新统计。

代码：

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #include
               
                #include
                
                 #include
                 
                  #include
                  using namespace std;#define INF 0x3f3f3f3f#define CLR(x,y) memset(x,y,sizeof(x))#define LC(x) (x<<1)#define RC(x) ((x<<1)+1)#define MID(x,y) ((x+y)>>1)typedef pair
                   
                     pii;typedef long long LL;const double PI=acos(-1.0);const int N=100010;const int M=50010;struct info{ int l,r; int id,b; bool operator<(const info &t)const { if(b==t.b) return r
                    
                     Q[i].l) { --L; ++vis[arr[L]]; if(vis[arr[L]]==1) ++temp; } while (L
                     
                      Q[i].r) { --vis[arr[R]]; if(vis[arr[R]]==0) --temp; --R; } while (R

转载于:https://www.cnblogs.com/Blackops/p/5843059.html

你可能感兴趣的文章