JOIN
 Revision History
 Select a Forum     Round Tables New Member Discussions News Discussions Algorithm Matches Marathon Matches NASA Tournament Lab TopCoder Cookbook High School Matches Sponsor Discussions Development Forums Design Forums Search My Post History  |  My Watches  |  User Settings Forums Round Tables External Competitions Re: Persistent Set Revision History (1 edit)
 Re: Persistent Set (response to post by Egor) http://www.spoj.pl/problems/DQUERY can be solved using some kind of persistent set, not a persistent balanced search tree but a persistent segment tree, maybe you can find it useful. For this problem there is an offline solution using a Binary Indexed Tree, but with a persistent data structure queries can be answered online.Code in edit...
 Re: Persistent Set (response to post by Egor) http://www.spoj.pl/problems/DQUERY can be solved using some kind of persistent set, not a persistent balanced search tree but a persistent segment tree, maybe you can find it useful. For this problem there is an offline solution using a Binary Indexed Tree, but with a persistent data structure queries can be answered online.```/* Alfonso2 Peterssen (mukel) 8 - 1 - 2008 SPOJ "DQUERY" Online algorithm Preprocessing: O(n lg n) Query: O(lg n) Memory: O(n lg n) */ #include #include   using std::map;   const int MAXN = 40000, MAXLGN = 16;   int N, Q; map< int, int > pos; int tree[MAXN]; int cant; struct node { int val, L, R, size; } buff[2 * MAXN * MAXLGN];   int build( int lo, int hi ) { if ( lo > hi ) return 0;   int idx = ++cant; int mid = ( lo + hi ) / 2; buff[idx] = (node){ mid, build( lo, mid - 1 ), build( mid + 1, hi ), 0 }; return idx; }   int update( int x, int val, int amount ) {   if ( x == 0 ) return 0;   int idx = ++cant; int L = buff[x].L; int R = buff[x].R; if ( val < buff[x].val ) L = update( L, val, amount ); if ( val > buff[x].val ) R = update( R, val, amount ); buff[idx] = (node){ buff[x].val, L, R, buff[x].size + amount };   return idx; }   int query( int x, int val ) { if ( val < buff[x].val ) return query( buff[x].L, val ) + buff[x].size - buff[ buff[x].L ].size;   if ( val > buff[x].val ) return query( buff[x].R, val );   return buff[x].size - buff[ buff[x].L ].size; }   int main() {   scanf( "%d", &N );   tree[0] = build( 1, N ); for ( int i = 1; i <= N; i++ ) { int x, posx; scanf( "%d", &x ); posx = pos[x]; if ( posx != 0 ) tree[i] = update( update( tree[i - 1], posx, -1 ), i, +1 ); else tree[i] = update( tree[i - 1], i, +1 ); pos[x] = i; }   scanf( "%d", &Q ); while ( Q-- ) { int lo, hi; scanf( "%d %d", &lo, &hi ); printf( "%d\n", query( tree[hi], lo ) ); }   return 0; }   ```