uva 11990 块状链表

  1 #include <algorithm>
  2 #include <iostream>
  3 #include <cstring>
  4 #include <cstdio>
  5 #include <cmath>
  6 using namespace std;
  7 
  8 typedef long long ll;
  9 const int INF = 9999999;
 10 const int N = 200001;
 11 const int M = 1000;
 12 int b[M][M];
 13 int sz[M];
 14 int a[N];
 15 int d[N];
 16 int n, m, ps, k;
 17 
 18 void remove( int num )
 19 {
 20     int pos = d[num];
 21     int cur = pos / ps;
 22     int w = lower_bound( b[cur], b[cur] + sz[cur], num ) - b[cur];
 23     for ( int i = w; i < sz[cur] - 1; i++ )
 24     {
 25         b[cur][i] = b[cur][i + 1];
 26     }
 27     sz[cur]--;
 28     a[d[num]] = INF;
 29 }
 30 
 31 int query( int num )
 32 {
 33     int pos = d[num];
 34     int cur = pos / ps;
 35     int s = 0, c = 0;
 36     for ( int i = 0; i < cur; i++ )
 37     {
 38         if ( sz[i] )
 39         {
 40             s += sz[i];
 41             c += upper_bound( b[i], b[i] + sz[i], num ) - b[i];
 42         }
 43     }
 44     for ( int i = cur * ps; i < pos; i++ )
 45     {
 46         if ( a[i] != INF )
 47         {
 48             s++;
 49             if ( a[i] < num ) c++;
 50         }
 51     }
 52     s -= c;
 53     for ( int i = cur + 1; i < k; i++ )
 54     {
 55         if ( sz[i] )
 56         {
 57             s += upper_bound( b[i], b[i] + sz[i], num ) - b[i];
 58         }
 59     }
 60     int bound = min( n, ( cur + 1 ) * ps );
 61     for ( int i = pos + 1; i < bound; i++ )
 62     {
 63         if ( a[i] < num )
 64         {
 65             s++;
 66         }
 67     }
 68     return s;
 69 }
 70 
 71 int main ()
 72 {
 73     while ( scanf("%d%d", &n, &m) != EOF )
 74     {
 75         ps = 800;
 76         for ( int i = 0; i < n; i++ )
 77         {
 78             scanf("%d", &a[i]);
 79             b[i / ps][i % ps] = a[i];
 80             d[a[i]] = i;
 81         }
 82         k = ( n + ps - 1 ) / ps;
 83         for ( int i = 0; i < k - 1; i++ )
 84         {
 85             sz[i] = ps;
 86             sort( b[i], b[i] + sz[i] );
 87         }
 88         sz[k - 1] = n - ( k - 1 ) * ps;
 89         sort( b[k - 1], b[k - 1] + sz[k - 1] );
 90         ll ans = 0;
 91         for ( int i = 1; i <= n; i++ )
 92         {
 93             ans += query(i);
 94         }
 95         ans = ans / 2;
 96         for ( int i = 0; i < m; i++ )
 97         {
 98             printf("%lld\n", ans);
 99             int tmp;
100             scanf("%d", &tmp);
101             ans -= query(tmp);
102             remove(tmp);
103         }
104     }
105     return 0;
106 }