题目链接
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 题意：现在有n个数，编号1到n，但是它们不是按顺序排列，现在有m次询问，每次询问给出个(l,r)；问在这个区间内连续的块有多少个，单个也算连续。拿样例解释一下：3 1 2 5 4，第二次询问(2,4)。这个区间的数有（1 2 5）可以分成(1,2),(5)两个块。所以第二次询问答案为2。
题解：首先我们将所有的查询区间全部按照右端点排序，排完序然后从左到右依次查询。我们用一个sum数组来记录（sum[i]表示1-i可以分成多少块）pos数组存num[i]的位置。现在我们就要用树状数组为维护了。首先题中说数字i和i-1,i+1都是相连的。我们现在假设当前i出现的区间i-1,i+1都未出现，所以我们直接用树状数组维护+1。现在就要考虑两边的数出现在当前区间了，要是num[i]+1出现在当前区间，我们就需要在num[i]+1的位置用树状数组维护全部-1.因为两个数在一个区间的话，说明两个数可以合成一个块，现在两个位置都因之前的假设全部都加了1，现在两个可以合成一个块，所以其中一个的位置上要-1。num[i]-1的情况和num[i]+1相同，要是判断在当前区间，直接用树状数组维护。
#include <iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<map>
#include<queue>
#include<set>
#include<cmath>
#include<stack>
#include<string>
const int maxn=1e5+10;
const int mod=1e9+7;
const int inf=1e8;
#define me(a,b) memset(a,b,sizeof(a))
#define lowbit(x) x&(-x)
#define mid (l+r)/2
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
typedef long long ll;
using namespace std;
int sum[maxn],n,m;
struct node
{
int l,r,i;
bool friend operator<(node a,node b)
{
return a.r<b.r;
}
}a[maxn];
int get_sum(int x)
{
int ans=0;
while(x)
{
ans+=sum[x];
x-=lowbit(x);
}
return ans;
}
void add(int i,int x)
{
while(i<=n)
{
sum[i]+=x;
i+=lowbit(i);
}
}
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
int num[maxn],pos[maxn],ans[maxn];
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
{
scanf("%d",&num[i]);
pos[num[i]]=i;
}
for(int i=1;i<=m;i++)
{
scanf("%d%d",&a[i].l,&a[i].r);
a[i].i=i;
}
sort(a+1,a+m+1);
me(sum,0);
int j=1;
for(int i=1;i<=n;i++)
{
add(i,1);
if(num[i]<n&&pos[num[i]+1]<i)//处理当前数的后一个数
add(pos[num[i]+1],-1);
if(num[i]>1&&pos[num[i]-1]<i)//处理当前数的前一个数
add(pos[num[i]-1],-1);
while(j<=n&&a[j].r==i)///这就是为啥区间要按照r从小到大排序.
{
ans[a[j].i]=get_sum(a[j].r)-get_sum(a[j].l-1);
j++;
}
}
for(int i=1;i<=m;i++)
printf("%d\n",ans[i]);
}
return 0;
}