HDU 4262 Juggler

http://acm.hdu.edu.cn/showproblem.php?pid=4262

树状数组更新点的位置，并可以求出两点之间的有多少球

View Code

 1 #include <stdio.h>
 2 #define maxn  100001
 3 int ans[maxn], n, b[maxn];
 4 
 5 int lowbit(int x)
 6 {
 7     return x & (-x);
 8 }
 9 
10 void mod(int x, int data)
11 {
12     int i;
13     for(i = x; i <= n; i+=lowbit(i))
14     ans[i] += data;
15 }
16 
17 int getSum(int x)
18 {
19     int i, sum=0;
20     for(i = x; i > 0; i -= lowbit(i))
21        sum += ans[i];
22     return  sum;   
23 }
24 
25 int abs(int a)
26 {
27     if(a < 0)  return -a;
28     return a;
29 }
30 
31 int main()
32 {
33     long long  m, i, j, k, l, mark, sum, temp;
34     while(~scanf("%lld",&n), n)
35     {
36         for(i = 1; i <= n; i++)
37         {
38             scanf("%lld",&m);
39             b[m] = i;
40             ans[i] = lowbit(i);
41         }
42         mark = 1;
43         sum = 0;
44         for(i = 1; i <= n; i++)
45         {
46             if(mark != b[i])
47             {
48                 temp = abs(getSum(mark - 1)-getSum(b[i] - 1));
49                 sum += (temp > (n - i + 1 - temp ) ? (n - i + 1 - temp) : temp);
50             }
51             mark = b[i];
52             mod(b[i], -1);
53         }
54         sum += n;
55         printf("%I64d\n",sum);
56     }
57     return 0;
58 }