题目链接：

　　

解题思路：

　　刚开始做的是，用hash离散化复杂度O(n*m)，感觉会Tle，不死心就尝试了一下，果然华丽丽的T了。

　　然后搜了一下，发现了莫队算法，感觉莫涛聚聚真是一个人才。啧啧啧啧~

　　莫队算法是一个用数组就可以轻易实现的神奇数据结构，可以处理一类无修改的离线区间查询问题(PS:暂时还没有遇到莫队解决更新区间查询的问题)

　　莫队算法可以在O(1)，实现[l, r]到[l, r±1] / [l±1, r]的转移，然后我们就可以对所有查询分sqrt(n)块，把每个查询所在的块号当做第一关键字，右端点作为第二关键字升序排列。

　　然后进行状态转移即可。

　　时间复杂度O(n*sqrt(n))：当i与i+1在同一个块内，则L最多移动sqrt(n),R最多移动n，所以复杂度为O(n*sqrt(n)).

　　　　　　　　　　　　　　当i与i+1不在同一块内，则L最多移动2*sqrt(n),R最多移动n，复杂度为O(n*sqrt(n)).

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 #include 
        
          5 #include 
         
           6 using namespace std; 7 const int maxn = 500010; 8 typedef long long LL; 9 struct node10 {11     LL r, l, index;12 }q[maxn];13 LL a[maxn], vis[maxn], ans[maxn][2];14 LL n, m, lb;15 bool cmp (node a, node b)16 {17     if (a.l/lb == b.l/lb)18         return a.r < b.r;19     return a.l < b.l;20 }21 LL gcd (LL a, LL b)22 {23     return b?gcd(b, a%b):a;24 }25 int main ()26 {27     while (scanf ("%lld %lld", &n, &m) != EOF)28     {29         for (int i=1; i<=n; i++)30             scanf ("%lld", &a[i]);31         for (int i=0; i
          
            q[i].r)52 {53 vis[a[r]] --;54 res -= vis[a[r]];55 r --;56 }57 while (l < q[i].l)58 {59 vis[a[l]] --;60 res -= vis[a[l]];61 l ++;62 }63 while (l > q[i].l)64 {65 l --;66 res += vis[a[l]];67 vis[a[l]] ++;68 }69 LL mu = (q[i].r - q[i].l + 1)*(q[i].r - q[i].l)/2;70 if (!res)71 {72 ans[q[i].index][0] = 0;73 ans[q[i].index][1] = 1;74 continue;75 }76 LL num = gcd (res, mu);77 ans[q[i].index][0] = res / num;78 ans[q[i].index][1] = mu / num;79 }80 for (int i=0; i