当前位置：首页 > news >正文

poj 2828 块状链表 OR 线段树 OR 树状数组

news 来源：原创 2024/5/19 20:02:43

这个题是真正可以体现出块状链表的优点。数组定位快但是插入慢，而链表插入快却定位慢。块状链表正是结合了数组和链表的优点将定位和插入的复杂度变成了sqrt(n)。

块状链表：

 1 #include <iostream>
 2 #include <cstring>
 3 #include <cstdio>
 4 using namespace std;
 5 
 6 const int N = 750;
 7 int b[N][N];
 8 int sz[N];
 9 int next[N];
10 int ps;
11 int bl;
12 
13 void init()
14 {
15     bl = 1;
16     ps = 550;
17     memset( sz, 0, sizeof(sz) );
18     memset( next, -1, sizeof(next) );
19 }
20 
21 void spilt( int cur )
22 {
23     int tmp = next[cur];
24     int ncur = next[cur] = bl++;
25     next[ncur] = tmp;
26     for ( int i = sz[cur] / 2; i < sz[cur]; i++ )
27     {
28         b[ncur][sz[ncur]++] = b[cur][i];
29     }
30     sz[cur] = sz[cur] / 2;
31 }
32 
33 void insert( int pos, int val )
34 {
35     int cur = 0, p = sz[cur];
36     while ( p < pos + 1 && next[cur] != -1 )
37     {
38         cur = next[cur];
39         p += sz[cur];
40     }
41     if ( p < pos + 1 )
42     {
43         b[cur][sz[cur]++] = val;
44     }
45     else
46     {
47         p -= sz[cur];
48         pos -= p;
49         for ( int j = sz[cur] - 1; j >= pos; j-- )
50         {
51             b[cur][j + 1] = b[cur][j];
52         }
53         b[cur][pos] = val;
54         sz[cur]++;
55     }
56     if ( sz[cur] > ps ) spilt(cur);
57 }
58 
59 int main ()
60 {
61     int n;
62     while ( scanf("%d", &n) != EOF )
63     {
64         init();
65         for ( int i = 0; i < n; i++ )
66         {
67             int pos, val;
68             scanf("%d%d", &pos, &val);
69             insert( pos, val );
70         }
71         int cnt = 0;
72         for ( int i = 0; i != -1; i = next[i] )
73         {
74             for ( int j = 0; j < sz[i]; j++ )
75             {
76                 printf("%d", b[i][j]);
77                 cnt++;
78                 if ( cnt != n )
79                 {
80                     putchar(' ');
81                 }
82                 else
83                 {
84                     putchar('\n');
85                 }
86             }
87         }
88     }
89     return 0;
90 }

线段树：

 1 #include <iostream>
 2 #include <cstring>
 3 #include <cstdio>
 4 using namespace std;
 5 
 6 const int N = 200001;
 7 int ans[N];
 8 int n;
 9 
10 struct X
11 {
12     int pos, val;
13 } x[N];
14 
15 struct Node 
16 {
17     int l, r, sum;
18 } node[N << 2];
19 
20 void pushup( int i )
21 {
22     node[i].sum = node[i << 1].sum + node[i << 1 | 1].sum;
23 }
24 
25 void build( int i, int l, int r )
26 {
27     node[i].l = l, node[i].r = r, node[i].sum = node[i].r - node[i].l + 1;
28     if ( l == r ) return ;
29     int mid = ( l + r ) >> 1;    
30     build( i << 1, l, mid );
31     build( i << 1 | 1, mid + 1, r );
32 }
33 
34 void update( int i, int pos, int val )
35 {
36     if ( node[i].l == pos && node[i].r == pos )
37     {
38         node[i].sum = val;
39         return ;
40     }
41     int mid = ( node[i].l + node[i].r ) >> 1;
42     if ( pos <= mid )
43     {
44         update( i << 1, pos, val );
45     }
46     else
47     {
48         update( i << 1 | 1, pos, val );
49     }
50     pushup(i);
51 }
52 
53 int query( int i, int v )
54 {
55     if ( node[i].l == node[i].r ) return node[i].l;
56     if ( node[i << 1].sum >= v ) return query( i << 1, v );
57     return query( i << 1 | 1, v - node[i << 1].sum );
58 }
59 
60 int main ()
61 {
62     while ( scanf("%d", &n) != EOF )
63     {
64         for ( int i = 1; i <= n; i++ )
65         {
66             scanf("%d%d", &x[i].pos, &x[i].val);
67             x[i].pos++;
68         }
69         build( 1, 1, n );
70         for ( int i = n; i >= 1; i-- )
71         {
72             int tmp = query( 1, x[i].pos );
73             ans[tmp] = x[i].val;
74             update( 1, tmp, 0 );
75         }    
76         for ( int i = 1; i < n; i++ )
77         {
78             printf("%d ", ans[i]);
79         }    
80         printf("%d\n", ans[n]);
81     }
82     return 0;
83 }

树状数组：

 1 #include <iostream>
 2 #include <cstring>
 3 #include <cstdio>
 4 using namespace std;
 5 
 6 const int N = 200001;
 7 int c[N];
 8 int ans[N];
 9 int n;
10 
11 struct X
12 {
13     int pos, val;
14 } x[N];
15 
16 int lb( int i )
17 {
18     return i & -i;
19 }
20 
21 void update( int i, int v )
22 {
23     while ( i <= n )
24     {
25         c[i] += v;
26         i += lb(i);
27     }
28 }
29 
30 int query( int k )
31 {
32     int ans = 0, cnt = 0;
33     for ( int i = 17; i >= 0; i-- )
34     {
35         ans += ( 1 << i );
36         if ( ans >= n || cnt + c[ans] >= k )
37         {
38             ans -= ( 1 << i );
39         }
40         else
41         {
42             cnt += c[ans];
43         }
44     }
45     return ans + 1;
46 }
47 
48 int main ()
49 {
50     while ( scanf("%d", &n) != EOF )
51     {
52         memset( c, 0, sizeof(c) );
53         for ( int i = 1; i <= n; i++ )
54         {
55             scanf("%d%d", &x[i].pos, &x[i].val);
56             x[i].pos++;
57             update( i, 1 );
58         }
59         for ( int i = n; i >= 1; i-- )
60         {
61             int tmp = query( x[i].pos );
62             ans[tmp] = x[i].val;
63             update( tmp, -1 );
64         }    
65         for ( int i = 1; i < n; i++ )
66         {
67             printf("%d ", ans[i]);
68         }    
69         printf("%d\n", ans[n]);
70     }
71     return 0;
72 }