实际上就是问这个区间编号连续的段的个数，假如一个编号连续的段有(a+b)个人，我把他们分在同一组能得到的分值为(a+b)^2，而把他们分成人数为a和b的两组的话，得到的分值就是a^2+b^2，显然(a+b)^2 > a^2+b^2，所以对于每个区间，尽可能把他们分成尽量少的组。
考虑把这些数从后往前添加，每添加一个数num[i]，如果num[i]+1或者num[i]-1有且只有一个已经存在，则段数不变；如果num[i]+1和num[i]-1同时存在，则段数-1，如果都不在，则段数+1。
对于每个数num[i]，我们记录把它添加进去的时候，它对段数产生的影响为c[i]( 即插入num[i]时对区间[i, N]的段数产生的影响 )，查询就是求c[i]的区间和。
对于询问我们做离线处理，把每个询问按右端点从大到小排序，从后往前扫描，每次把询问右端点之外的数删掉，根据其是否会产生影响对c[i]进行更新。
Sum( Query[i].r ) - Sum( Query[i].l - 1 ) 即为答案。
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm> using namespace std; const int MAXN = ; struct node
{
int l, r, id;
}; int N, Q;
node qry[MAXN]; //查询
int C[MAXN]; //树状数组
int num[MAXN]; //原数组
int addr[MAXN]; //每个数在哪个位置
int ans[MAXN]; //记录答案
bool use[MAXN]; //该数是否存在 bool cmp( node a, node b )
{
return a.r > b.r;
} int lowbit( int x )
{
return x & (-x);
} int Query( int x )
{
int res = ;
while ( x > )
{
res += C[x];
x -= lowbit(x);
}
return res;
} void Update( int x, int val )
{
while ( x <= N )
{
C[x] += val;
x += lowbit(x);
}
return;
} void init()
{
memset( C, , sizeof(C) );
memset( use, false, sizeof(use) ); for ( int i = N; i > ; --i )
{
if ( use[ num[i] - ] && use[ num[i] + ] )
{
Update( i, - );
}
else if ( !( use[ num[i] - ] || use[ num[i] + ] ) )
{
Update( i, );
}
use[ num[i] ] = true;
}
return;
} void solved()
{
int j = N;
for ( int i = ; i < Q; ++i )
{
while ( j > 0 && j > qry[i].r )
{
if ( num[j] > && addr[ num[j] - ] < j )
{
Update( addr[ num[j] - ], );
}
if ( num[j] < N && addr[ num[j] + ] < j )
{
Update( addr[ num[j] + ], );
}
--j;
}
ans[ qry[i].id ] = Query( qry[i].r ) - Query( qry[i].l - );
} for ( int i = ; i < Q; ++i )
printf( "%d\n", ans[i] ); return;
} int main()
{
int T;
scanf( "%d", &T );
while ( T-- )
{
scanf( "%d%d", &N, &Q );
for ( int i = ; i <= N; ++i )
{
scanf( "%d", &num[i] );
addr[ num[i] ] = i;
}
for ( int i = ; i < Q; ++i )
{
scanf("%d%d", &qry[i].l, &qry[i].r );
qry[i].id = i;
}
sort( qry, qry + Q, cmp ); init();
solved();
}
return ;
}