Group（分塊+莫隊）

There are n men ,every man has an ID(1…n).their ID is unique. Whose ID is i and i-1 are friends, Whose ID is i and i+1 are friends. These n men stand in line. Now we select an interval of men to make some group. K men in a group can create K*K value. The value of an interval is sum of these value of groups. The people of same group’s id must be continuous. Now we chose an interval of men and want to know there should be how many groups so the value of interval is max.

Input

First line is T indicate the case number.

For each case first line is n, m(1<=n ,m<=100000) indicate there are n men and m query.

Then a line have n number indicate the ID of men from left to right.

Next m line each line has two number L,R(1<=L<=R<=n),mean we want to know the answer of [L,R].

Output

For every query output a number indicate there should be how many group so that the sum of value is max.

Sample Input

1

5 2

3 1 2 5 4

1 5

2 4

Sample Output

1

2

題意：

問所給區間的連續的序列個數，如：3 1 2，6 7， 9都算連續的序列

思路：

n最大1e5，m最大1e5，若純暴力，1e10，會爆，很顯然普通分塊解決不了，

是以用了莫隊，先分塊，再把所給區間排序，

利用l，r的移動，數組走一遍求出所有離線區間的結果，最後一起輸出

離線就是預先已經知道了已知和所有要求的情況，這是莫隊必不可少的使用條件，不然拿啥排序呀

關于區間的排序：

區間的排序，先看left是否在同一塊，

若在一塊，即left距離近，那麼左邊移來移去沒啥大不了，就按right從小到大排

若不在一塊，即left距離遠，左邊移來移去有風險，就按left從小到大排

#include <bits/stdc++.h>

using namespace std;

int a[100005], belong[100005], coun[100005];
struct node
{
    int left, right, num;
}str[100005];

bool cmp(struct node x, struct node y)
{
    if(belong[x.left]==belong[y.left]) return x.right < y.right;
    else return x.left < y.left;
}

int add(int n, int sum)
{
    coun[n] = 1;
    if(coun[n-1]&&coun[n+1]) sum--;          //連接配接兩序列成為一個序列
    else if(!coun[n-1]&&!coun[n+1]) sum++;     //前無古人後無來者，本身是一個序列
    return sum;
}

int subtract(int n, int sum)
{
    coun[n] = 0;
    if(coun[n-1]&&coun[n+1]) sum++;
    else if(!coun[n-1]&&!coun[n+1]) sum--;
    return sum;
}

int main()
{
    int n, m, t, re[100005], i, temp, l, r, sum;
    scanf("%d", &t);
    while(t--)
    {
        scanf("%d %d", &n, &m);
        temp = sqrt(n);
        for(i=1; i<=n; i++)
        {
            scanf("%d", &a[i]);
            belong[i] = (i-1) / temp + 1;
        }
        for(i=1; i<=m; i++)
        {
            str[i].num = i;
            scanf("%d %d", &str[i].left, &str[i].right);
        }
        sort(str+1, str+m+1, cmp);
        l = 1;      //先走右，再走左
        r = 0;
        sum = 0;
        memset(coun, 0, sizeof(coun));
        for(i=1; i<=m; i++)
        {
            while(r < str[i].right)
            {
                r++;                  //最終的右端點應該包括所求區間的右端點
                sum = add(a[r], sum);
            }
            while(r > str[i].right)
            {
                sum = subtract(a[r], sum);
                r--;
            }
            while(l < str[i].left)
            {
                sum = subtract(a[l], sum);
                l++;
            }
            while(l > str[i].left)
            {
                l--;
                sum = add(a[l], sum);
            }
            re[str[i].num] = sum;
        }
        for(i=1; i<=m; i++)
        {
            printf("%d\n", re[i]);
        }
    }
    return 0;
}