提交时间:2024-03-31 09:09:56
运行 ID: 27812
#include <bits/stdc++.h> #define lson ( pos << 1 ) #define rson ( pos << 1 | 1 ) using namespace std ; int n , x , a[1000005] ; struct SegTree { int max ; int min ; }tre[4000005]; struct ans{ int max ; int min ; }; void pushup( int pos ){ tre[pos].max = max( tre[lson].max , tre[rson].max ); tre[pos].min = min( tre[lson].min , tre[rson].min ); return ; } void build( int pos , int l , int r ){ if( l == r ){ tre[pos].max = a[l] ; tre[pos].min = a[l] ; return ; } int mid = ( l + r ) >> 1 ; build( lson , l , mid ); build( rson , mid+1 , r ); pushup( pos ); return ; } ans query( int pos , int l , int r , int ql , int qr ){ ans res ; res.max = 0 ; res.min = 1e9 + 1 ; if( ql <= l && qr >= r ){ res.max = tre[pos].max ; res.min = tre[pos].min ; return res ; } int mid = ( l + r ) >> 1 ; ans re ; if( ql <= mid ){ re = query( lson , l , mid , ql , qr ); res.max = max( re.max , res.max ); res.min = min( re.min , res.min ); } if( qr > mid ){ re = query( rson , mid+1 , r , ql , qr ); res.max = max( re.max , res.max ); res.min = min( re.min , res.min ); } return res ; } int main(){ scanf("%d%d" , &n ,&x ); int cnt = 0 ; for( int i = 1 ; i <= n ; ++ i ){ scanf("%d" , &a[i] ); if(( a[i] << 1 ) == x ){ cnt ++ ; } } build( 1 , 1 , n ); for( int i = 1 ; i <= n ; ++ i ){ for( int j = i+1 ; j <= n ; ++ j ){ ans res ; res = query( 1 , 1 , n , i , j ); if( res.max + res.min == x ){ cnt ++ ; } } } printf("%d" , cnt ); return 0 ; }