链接：

来源：牛客网

时间限制：C/C++ 2秒，其他语言4秒

空间限制：C/C++ 524288K，其他语言1048576K

64bit IO Format: %lld

题目描述

Given a sequence of integers a

₁, a

₂, ..., a

_n and q pairs of integers (l

₁, r

₁), (l

₂, r

₂), ..., (l

_q, r

_q), find count(l

₁, r

₁), count(l

₂, r

₂), ..., count(l

_q, r

_q) where count(i, j) is the number of different integers among a

₁, a

₂, ..., a

_i, a

_j, a

_{j + 1}, ..., a

_n.

输入描述:

The input consists of several test cases and is terminated by end-of-file. The first line of each test cases contains two integers n and q. The second line contains n integers a

₁

, a

₂

, ..., a

_n

. The i-th of the following q lines contains two integers l

_i

and r

_i

.

输出描述:

For each test case, print q integers which denote the result.

示例1

输入

3 21 2 11 21 34 11 2 3 41 3

输出

213

备注:

* 1 ≤ n, q ≤ 10

⁵

* 1 ≤ a

_i

≤ n * 1 ≤ l

_i

, r

_i

≤ n * The number of test cases does not exceed 10. 骚操作:直接把数组*2 然后求1-L,R-N 就变成 求R-L+N之间的不同数的个数了；注意，主席树会TLE；要用线段数组+离线

#include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
          
         
        
       
      

 

也可以莫队加上读入挂

#include
      
        using namespace std;int n,q,a[100005];int L,R,ans;struct node{    int l,r,id;};node temp[100005];int sum[1000005];int anw[1000005];int block[100005];int read(){    char ch=' ';    int ans=0;    while(ch<'0' || ch>'9')        ch=getchar();    while(ch<='9' && ch>='0')    {        ans=ans*10+ch-'0';        ch=getchar();    }    return ans;}int cmp(node a,node b){    if(block[a.l]==block[b.l])return block[a.r]
       
        temp[i].r)R--,add(a[R]);            while(L>temp[i].l)del(a[L]),L--;            while(R