RE求助
查看原帖
RE求助
281668
FOX_konata楼主2021/11/14 20:43

代码一直RE,无论是本地还是IDE都能正常运行,求调

#include <bits/stdc++.h>
#define For( i , j , k ) for( ll i = ( j ) ; i <= ( k ) ; ++ i )
#define For__( i , j , k ) for( ll i = ( j ) ; i >= ( k ) ; -- i )
#define Fore( i , j , k ) for( ll i = j ; i ; i = k )
#define ll long long
#define lf double
#define llf long double
#define random( l , r ) ( ( 1ll * rand() * rand() % ( r - l + 1 ) + rand() ) % ( r - l + 1 ) + l )
using namespace std;
//-------------------------Fastio-------------------------//
template < typename T >
inline T read( T &num ){
	num = 0 ; T f = 1 ; char c = ' ';
	while( c < '0' || c > '9' ) if( ( c = getchar() ) == '-' ) f = -1;
	while( c >= '0' && c <= '9' ) num = ( num << 1 ) + ( num << 3 ) + ( c ^ 48 ) , c = getchar();
	num *= f;
	return num;
}
//-------------------------Fastio end-------------------------//
const ll maxn = 2e5 + 5;
const ll INF = ( 1ll << 60 );
ll n , m;
char c;
ll a[ maxn ] , sum[ maxn ];
namespace Line_Tree{//线段树 
	#define ls ( p << 1 )
	#define rs ( p << 1 | 1 )
	struct Tree{
		ll mins , tag;
		Tree( ll mins_ = INF ){
			mins = mins_;
			tag = 0;
			return ;
		}
		Tree operator + ( const Tree &x ) const{
			Tree ans;
			ans.mins = min( mins , x.mins );
			return ans;
		}
	}trees[ maxn << 2 ];
	inline void push_up( ll p ){
		trees[ p ].mins = min( trees[ ls ].mins , trees[ rs ].mins );
		return ;
	}
	inline void f( ll l , ll r , ll k , ll p ){
		trees[ p ].mins += k;
		trees[ p ].tag += k;
		return ;
	}
	inline void push_down( ll l , ll r , ll p ){
		ll k = trees[ p ].tag;
		if( !k ) return ;
		ll mid = l + r >> 1;
		f( l , mid , k , ls );
		f( mid + 1 , r , k , rs );
		trees[ p ].tag = 0;
		return ;
	}
	inline void build( ll l , ll r , ll p ){
		if( l == r ){
			trees[ p ].mins = sum[ l ];
			return ;
		}
		ll mid = l + r >> 1;
		build( 1 , mid , ls );
		build( mid + 1 , r , rs );
		push_up( p );
		return ;
	}
	inline void update( ll l , ll r , ll x , ll y , ll k , ll p ){
		if( x <= l && r <= y ){
			f( l , r , k , p );
			return ;
		}
		push_down( l , r , p );
		ll mid = l + r >> 1;
		if( x <= mid ) update( l , mid , x , y , k , ls );
		if( mid < y ) update( mid + 1 , r , x , y , k , rs );
		push_up( p );
		return ;
	}
	inline ll query( ll l , ll r , ll x , ll y , ll p ){
		if( x <= l && r <= y )
			return trees[ p ].mins;
		push_down( l , r , p ); 
		ll mid = l + r >> 1;
		ll sum = INF;
		if( x <= mid ) sum = min( sum , query( l , mid , x , y , ls ) );
		if( mid < y ) sum = min( sum , query( mid + 1 , r , x , y , rs ) );
		return sum;
	}
	#undef ls
	#undef rs
};
inline bool check(){
	ll all = Line_Tree :: trees[ 1 ].mins;
	ll ends = Line_Tree :: query( 1 , n , n , n , 1 );
	if( all >= 0 && ends == 0 ) return true;
	return false;
}
int main(){
	For( T , 1 , 10 ){
		printf( "Test %lld:\n" , T );//多组数据 
		read( n );
		For( i , 1 , n ){
            cin >> c;
			a[ i ] = c == '(' ? 1 : -1;//(为1,)为-1 
			sum[ i ] = sum[ i - 1 ] + a[ i ];//求前缀和 
		}//输入 
		Line_Tree :: build( 1 , n , 1 );//建树 
		read( m );//多次操作 
		ll opt;
		For( i , 1 , m ){
			read( opt );
			if( !opt )
				puts( check() ? "YES" : "NO" );
			else{
				Line_Tree :: update( 1 , n , opt , n , -2 * a[ opt ] , 1 );
				a[ opt ] *= -1;
			}
		}
	}
	return 0;
}
/*
4
()((
4
4
0
2
0
*/

2021/11/14 20:43
加载中...