Documentation/docs-sonyckson/tournament.cpp

   1 struct tournament {
   2     vector< int > f;
   3
   4     tournament() { f.resize( 2*off, 0 ); }
   5
   6     int query( int lo, int hi, int a = 0, int b = off, int x = 1 ) {
   7         if( a >= hi || b <= lo ) return 0;
   8         if( a >= lo && b <= hi ) return f[x];
   9
  10         int r = query( lo, hi, a, (a+b)/2, 2*x );
  11         int s = query( lo, hi, (a+b)/2, b, 2*x+1 );
  12
  13         return s ? s : r;
  14     }
  15
  16     void update( int x, int v ) {
  17         if( f[off+x] )
  18             f[off+x] = 0;
  19         else
  20             f[off+x] = v;
  21
  22         for( x = ( x+off ) / 2; x > 0; x /= 2 )
  23             f[x] = ( f[2*x+1] ? f[2*x+1] : f[2*x] );
  24     }
  25 };
  26
  27 tournament T;