題目大意：題面意思不解釋了，轉換成數學模型，就是問一段區間[l,r]有幾段連續的數，比如[2,3,1,4,6,7]那麼這段區間內有兩段，分別是1,2,3,4和6,7。
解題思路：由於詢問次數有100000次，所以我們直接處理[l,r]顯然不行。線段樹在線似乎也是做不了的。可以想到的是，如果我們從左到右一個個加進來，那麼對於加進來的第i個數num[i]，那麼它就能增加一個段（num[i]+1,和num[i]-1在之前都沒出現過），或者減少一個段（num[i]+1,和num[i]-1在之前都出現過），或者不增不減（num[i]+1,和num[i]-1在之前只出現過其中一個）。那麼我們要找的詢問的區間[l,r]內有多少個區間，就是詢問[l,r]內的數，增加了幾個這樣的段。但是直接詢問[l,r]內的數產生的段數是不可以的，因為對於[l,r]內的某一個數，有可能它所能產生的段數是跟l之前，或者r之後的數有關的。因此我們可以將詢問離線出來，按l排好序，每次詢問之前，將l之前的數產生的影響先清除掉，也就是對於某個在l之前的數，將它所能影響的後面的數能增加的段去除，對於之前的已經不用管了，因為我們按左端點排序，所以在清除某一個數時，它前面的數的影響之前已經處理掉了。然後從上一次插完的位置開始到r，把這之間的數插進去，如果上一次已經超過r了，也沒關系，我們會答r之前的總後就可以了，而l之前的數已經被清除掉，所以這個前綴後自然就是[l,r]的區間和。
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std ;
const int maxn = 111111 ;
struct Query
{
int l , r , ans ;
} p[maxn] ;
int pos[maxn] , vis[maxn] , c[maxn] , cnt[maxn] ;
int lowbit ( int x ) { return x & ( -x ) ; }
void update ( int pos , int v )
{
while ( pos < maxn - 10 )
{
c[pos] += v ;
pos += lowbit ( pos ) ;
}
}
int query ( int pos )
{
int ret = 0 ;
while ( pos > 0 )
{
ret += c[pos] ;
pos -= lowbit ( pos ) ;
}
return ret ;
}
int cmp ( int i , int j )
{
return p[i].l < p[j].l ;
}
int num[maxn] ;
int main ()
{
int i , j , k , m , n , cas ;
scanf ( "%d" , &cas ) ;
while ( cas -- )
{
scanf ( "%d%d" , &n , &m ) ;
for ( i = 1 ; i <= n ; i ++ ) scanf ( "%d" , &num[i] ) ;
for ( i = 1 ; i <= m ; i ++ )
{
scanf ( "%d%d" , &p[i].l , &p[i].r ) ;
pos[i] = i ;
}
memset ( vis , 0 , sizeof ( vis ) ) ;
memset ( c , 0 , sizeof ( c ) ) ;
memset ( cnt , 0 , sizeof ( cnt ) ) ;
sort ( pos + 1 , pos + m + 1 , cmp ) ;
int last1 = 1 , last2 = 1 ;
for ( i = 1 ; i <= m ; i ++ )
{
while ( last1 <= p[pos[i]].r )
{
int add = 1 ;
if ( vis[num[last1]-1] ) add -- ;
if ( vis[num[last1]+1] ) add -- ;
vis[num[last1]] = 1 ;
cnt[num[last1]] = last1 ;
update ( last1 , add ) ;
last1 ++ ;
}
while ( last2 < p[pos[i]].l )
{
if ( vis[num[last2]-1] ) update ( cnt[num[last2]-1] , 1 ) ;
if ( vis[num[last2]+1] ) update ( cnt[num[last2]+1] , 1 ) ;
update ( cnt[num[last2]] , -1 ) ;
vis[num[last2]] = 0 ;
last2 ++ ;
}
p[pos[i]].ans = query ( p[pos[i]].r ) ;
}
for ( i = 1 ; i <= m ; i ++ )
printf ( "%d\n" , p[i].ans ) ;
}
}
/*
10
10 5
1 3 5 7 9 2 4 6 8 10
1 10
2 9
3 8
4 7
5 6
10 5
1 3 5 7 9 10 8 6 4 2
1 10
2 9
3 8
4 7
5 6
10 5
1 2 3 4 5 6 7 8 9 10
1 10
2 9
3 8
4 7
5 6
*/
