sicily 1802 线段树

//第二个线段树 //原本想编个 [a+1=b]的树，空间2*Mx 交上去各种RE，将Mx改大各种WA //没办法，改做[a=b]的树，只改了一两个地方。。用小号竟然神奇AC了 = = rp //查下代码发现自己处理的时候 只处理 a+1 = b的地方(本来就这么设计的) //然后初始化的时候把所有节点值置为-1，rp由此诞生 #include <iostream> #include <cstring> #include <cstdio> #define Mx 100100 using namespace std; int t,n; int ca; //空行贡献一次PE int In;char ac[11]; bool _used[Mx]; inline int mn( int a,int b ) //注意-1 { if( a == -1 ) return b; if( b == -1 ) return a; return (a < b ? a : b); } struct Seq { int x,y; int l,u,value; //左树最靠近(0) 右树最靠近(Mx) 线段有效点最小距离 }seq[4*Mx+1]; void buildTree( int p,int x,int y ) { seq[p].x = x;seq[p].y = y; if( x == y ) return ; int mid = ( x + y ) / 2; buildTree( 2*p,x,mid ); buildTree( 2*p+1,mid+1,y ); } void add( int p,int z ) { int mid = ( seq[p].x + seq[p].y ) / 2; if( mid >= z ) { if( seq[p].l < z ) seq[p].l = z; if( seq[p].x + 1 < seq[p].y ) add( 2*p,z ); } else { if( seq[p].u > z ) seq[p].u = z; if( seq[p].x + 1 < seq[p].y ) add( 2*p+1,z ); } int kk = ( ( seq[p].l == 0 || seq[p].u == Mx ) ? -1 : (seq[p].u - seq[p].l ) ); //[a+1=b]的bug应该出在小数据的某[a==b]这了 if( seq[p].x + 1 == seq[p].y ) { seq[p].value = kk; return ; } int k = mn( seq[2*p].value,seq[2*p+1].value ); seq[p].value = mn( k,kk ); } void remove( int p,int z ) //remove考虑 l u值得修改即可 { int mid = ( seq[p].x + seq[p].y ) / 2; if( mid >= z ) { if( seq[p].l == z ) { for( int i = z-1;i >= seq[p].x;i-- ) { if( _used[i] ) { seq[p].l = i;break; } } if( seq[p].l == z ) { seq[p].l = 0; } } if( seq[p].x + 1 < seq[p].y ) remove( 2*p,z ); } else { if( seq[p].u == z ) { for( int i = z+1;i <= seq[p].y;i++ ) { if( _used[i] ) { seq[p].u = i;break; } } if( seq[p].u == z ) { seq[p].u = Mx; } } if( seq[p].x + 1 < seq[p].y ) remove( 2*p+1,z ); } int kk = ( ( seq[p].l == 0 || seq[p].u == Mx ) ? -1 : (seq[p].u - seq[p].l ) ); if( seq[p].x + 1 == seq[p].y ) { seq[p].value = kk; return ; } int k = mn( seq[2*p].value,seq[2*p+1].value ); seq[p].value = mn( k,kk ); } void pre_work( int p ) //初始化节点value { seq[p].l = 0; seq[p].u = Mx; seq[p].value = -1; //value[a,b] = -1 if( 2*p < 4 * Mx + 1 ) pre_work( 2*p ); if( 2*p+1 < 4 * Mx + 1 ) pre_work( 2*p+1 ); } int main() { //freopen( "1.txt","r",stdin ); scanf("%d",&t); buildTree( 1,1,100000 ); while( t-- ) { if( ca++ ) cout<<endl; pre_work(1); memset( _used,false,sizeof(_used) ); scanf( "%d",&n ); while( n-- ) { scanf( "%s",ac ); if( 0 == strcmp( ac,"generate" ) ) { scanf( "%d",&In ); if( !_used[In] ) add( 1,In ); _used[In] = true; } if( 0 == strcmp( ac,"remove" ) ) { scanf( "%d",&In ); if( _used[In] ) remove( 1,In ); _used[In] = false; } if( 0 == strcmp( ac,"query" ) ) { printf( "%d/n",seq[1].value ); } } } return 0; }