# POJ 1804 Brainman(5种解法，好题，【暴力】，【归并排序】，【线段树单点更新】，【树状数组】，【平衡树】)

## Brainman

 Time Limit: 1000MS Memory Limit: 30000K Total Submissions: 10575 Accepted: 5489

Description

Background
Raymond Babbitt drives his brother Charlie mad. Recently Raymond counted 246 toothpicks spilled all over the floor in an instant just by glancing at them. And he can even count Poker cards. Charlie would love to be able to do cool things like that, too. He wants to beat his brother in a similar task.

Problem
Here‘s what Charlie thinks of. Imagine you get a sequence of N numbers. The goal is to move the numbers around so that at the end the sequence is ordered. The only operation allowed is to swap two adjacent numbers. Let us try an example:Start with: 2 8 0 3
swap  (2 8) 8 2 0 3
swap  (2 0) 8 0 2 3
swap  (2 3) 8 0 3 2
swap  (8 0) 0 8 3 2
swap  (8 3) 0 3 8 2
swap  (8 2) 0 3 2 8
swap  (3 2) 0 2 3 8
swap  (3 8) 0 2 8 3
swap  (8 3) 0 2 3 8So the sequence (2 8 0 3) can be sorted with nine swaps of adjacent numbers. However, it is even possible to sort it with three such swaps:Start with: 2 8 0 3
swap  (8 0) 2 0 8 3
swap  (2 0) 0 2 8 3
swap  (8 3) 0 2 3 8The question is: What is the minimum number of swaps of adjacent numbers to sort a given sequence?Since Charlie does not have Raymond‘s mental capabilities, he decides to cheat. Here is where you come into play. He asks you to write a computer program for him that answers the question. Rest assured he will pay a very good prize for it.

Input

The first line contains the number of scenarios.
For every scenario, you are given a line containing first the length N (1 <= N <= 1000) of the sequence,followed by the N elements of the sequence (each element is an integer in [-1000000, 1000000]). All numbers in this line are separated by single blanks.

Output

Start the output for every scenario with a line containing "Scenario #i:", where i is the number of the scenario starting at 1. Then print a single line containing the minimal number of swaps of adjacent numbers that are necessary to sort the given sequence. Terminate the output for the scenario with a blank line.

Sample Input

4
4 2 8 0 3
10 0 1 2 3 4 5 6 7 8 9
6 -42 23 6 28 -100 65537
5 0 0 0 0 0

Sample Output

Scenario #1:
3

Scenario #2:
0

Scenario #3:
5

Scenario #4:
0

Source

TUD Programming Contest 2003, Darmstadt, Germany

<1>.暴力大法，时间复杂度为O(n^2)

<2>.归并排序法,时间复杂度为O(n*log n)

<3>.线段树单点更新，时间复杂度为O(log n)

1 #include <iostream>
2 #include <stdio.h>
3 using namespace std;
4 const int N=200020;
5 int a[N],b[N];
6 int main()
7 {
8     int n;
9     scanf("%d",&n);
10     for(int k=1;k<=n;k++)
11     {
12         int m;
13         scanf("%d",&m);
14         for(int i=1;i<=m;i++)
15             scanf("%d",&a[i]);
16             int ans=0;
17             for(int i=1;i<=m;i++)
18                 for(int j=i+1;j<=m;j++)
19                 if(a[i]>a[j])
20                 ans++;
21             printf("Scenario #%d:\n%d\n\n",k,ans);
22     }
23     return 0;
24 }

1 #include <iostream>
2 #include <cstdio>
3 #include <cstdlib>
4 using namespace std;
5 const int max_n = 1000 + 10;
6
7 int n, a[max_n];
8 int tmp[max_n], ans;
9
10 void merge(int *a, int *tmp, int l, int mid, int r)
11 {
12     if (l >= r)  return;
13     int i = l, j = mid + 1, k = 0;
14     int count = 0, flag = 0;
15     while (i <= mid && j <= r)
16     {
17         if (a[i] <= a[j])
18         {
19             tmp[k ++] = a[i++];
20             ans += j - mid - 1;
21         }else   tmp[k ++ ] =  a[j++];
22     }
23     while (i <= mid) tmp[k ++] = a[i++], ans += r- mid;
24     while (j <= r)       tmp[k ++] = a[j++];
25     for (i = 0; i != k; ++ i)   a[l + i] = tmp[i];
26 }
27
28 void mergesort(int *a, int *tmp, int l, int r)
29 {
30     if (l >= r)  return;
31     int mid = (l + r) / 2;
32     mergesort(a, tmp, l, mid);
33     mergesort(a, tmp , mid + 1, r);
34     merge(a, tmp, l, mid, r);
35 }
36
37 int main()
38 {
39     int tt;
40     scanf("%d", &tt);
41     for (int i = 1; i <= tt; ++ i)
42     {
43         cout<<"Scenario #"<<i<<":"<<endl;
44         scanf("%d", &n);
45         ans = 0;
46         for (int i = 0; i != n; ++ i)   scanf("%d", &a[i]);
47         mergesort(a, tmp, 0, n - 1);
48         cout<<ans<<endl<<endl;
49     }
50 }

n个数扫一边 遇到一个值i加到线段树上  查（i+1，n），再求和输出！

1 #include <map>
2 #include <iostream>
3 #include <set>
4 #include <cstdio>
5 #include <cstdlib>
6 using namespace std;
7
8 const int max_n = 1000 + 10;
9
10 int n;
11 int a[max_n], count;
12 map<int, int>G;
13 map<int, int>::iterator it;
14
15
16
17 struct node
18 {
19     int cd, key;
20     int ls, rs;
21     int L, R;
22     node():L(0),R(0),ls(0),rs(0),cd(0),key(0){};
23     void clear()
24     {
25         cd = key = 0;
26     }
27 }t[max_n * 3];
28 int tail = 1;
29
30
31 void init()
32 {
33     for (int i = 0; i != max_n * 3; ++ i)    t[i].clear();
34     G.clear();
35     scanf("%d", &n);
36     for (int i = 0; i != n; ++ i)
37     {
38         scanf("%d", &a[i]);
39         G[a[i]] = 0;
40     }
41     count = 0;
42     for (it = G.begin(); it != G.end(); ++ it)    it -> second = ++ count;
43 }
44
45
46
47 void make_tree(int now, int LL, int RR)
48 {
49     t[now].L = LL;
50     t[now].R = RR;
51     if (LL == RR)    return;
52     int mid = (LL + RR)/ 2;
53     make_tree(t[now].ls = ++ tail, LL, mid);
54     make_tree(t[now].rs = ++ tail, mid + 1, RR);
55 }
56
57 void tran(int now)
58 {
59     int left_son = t[now].ls, right_son = t[now].rs;
60     t[left_son].cd += t[now].cd;
61     t[right_son].cd += t[now].cd;
62     t[now].key += t[now].cd;
63     t[now].cd = 0;
64 }
65
66 void ins(int now, int LL, int RR)
67 {
68
69     tran(now);
70     if (t[now].L == LL && t[now].R == RR)
71     {
72         t[now].cd ++;
73         return;
74     }
75     t[now].key ++;
76     int mid = (t[now].L + t[now].R) / 2;
77     if (RR <= mid)    {ins(t[now].ls, LL, RR); return;}
78     if (mid < LL)    {ins(t[now].rs, LL, RR); return;}
79     ins(t[now].ls, LL, mid);
80     ins(t[now].rs, mid + 1, RR);
81 }
82
83 int find(int now, int LL, int RR)//因为题目的特殊性，只会找一个……
84 {
85     tran(now);
86     if (t[now].L == LL  && t[now].R == RR)    return t[now].key;
87     int mid = (t[now].L + t[now].R) / 2;
88     if (RR <= mid)    return find(t[now].ls, LL, RR);
89     if (mid < LL)    return find(t[now].rs, LL, RR);
90     cout<<"wtf?"<<endl;
91 }
92
93 void doit()
94 {
95     int ans=0;
96     for (int i = 0; i != n; ++ i)
97     {
98         int num = G[a[i]];
99         ans += find(1, num + 1, num + 1);
100         ins(1, 0, num);
101     }
102     cout<<ans<<endl;
103 }
104
105 int main()
106 {
107     int tt;
108     scanf("%d",&tt);
109     make_tree(1, 0, 1002);
110     for (int i = 1; i <= tt; ++ i)
111     {
112         cout<<"Scenario #"<<i<<":"<<endl;
113         init();
114         doit();
115         cout<<endl;
116     }
117 }

1 #include <cstdio>
2 #include <cstdlib>
3 #include <map>
4 #include <cstring>
5 using namespace std;
6 #define lowbit(k) ((k)&(-k))
7
8 const int max_n = 1000 + 10;
9 int n, a[max_n], s[max_n];
10 map<int, int>G;
11 map<int, int>::iterator it;
12 int count;
13 void init()
14 {
15     scanf("%d", &n);
16     G.clear();
17     count = 1;
18     memset(s, 0, sizeof(s));
19     for (int i = 0; i != n; ++ i)
20     {
21         scanf("%d", &a[i]);
22         G[a[i]] = 0;
23     }
24     for (it = G.begin(); it != G.end(); ++ it)    it -> second = ++ count;
25 }
26
27 void ins(int k)
28 {
29     s[k] += 1;
30     while ((k += lowbit(k)) <= 1000)    s[k] += 1;
31 }
32
33
35 {
36     int tot = s[k];
37     while (k -= lowbit(k))    tot += s[k];
39 }
40
41
42 void doit()
43 {
44     int ans = 0;
45     for (int i = 0; i != n; ++ i)
46     {
47         int num = G[a[i]];
49         ins(num);
50     }
51     printf("%d\n",ans);
52 }
53
54 int main()
55 {
56     int tt;
57     scanf("%d", &tt);
58     for (int i = 1; i <= tt; ++ i)
59     {
60         printf("Scenario #%d:\n",i);
61         init();
62         doit();
63         printf("\n");
64     }
65 }

1 #include <iostream>
2 #include <cstdio>
3 #include <cstdlib>
4 using namespace std;
5 const int max_n = 1000 + 10;
6
7 int n;
8 const int maxint = 0x7fffffff;
9
10 struct node
11 {
12     node *c[2];
13     int key;
14     int size;
15     node():key(0),size(0)
16     {
17         c[0] = c[1] = this;
18     }
19     node(int KEY_, node *a0, node *a1):
20     key(KEY_){c[0] =a0, c[1]=a1;}
21     node* rz(){return size = c[0]->size + c[1]->size + 1, this;}
22 }Tnull, *null=&Tnull;
23
24 struct splay
25 {
26     node *root;
27     splay()
28     {
29         root = (new node(*null)) -> rz();
30         root -> key = maxint;
31     }
32     void zig(int d)
33     {
34         node *t = root -> c[d];
35         root -> c[d]  = null -> c[d];
36         null -> c[d] = root;
37         root = t;
38     }
39     void zigzig(int d)
40     {
41         node *t = root -> c[d] -> c[d];
42         root -> c[d] -> c[d] = null -> c[d];
43         null -> c[d] = root -> c[d];
44         root -> c[d] = null -> c[d] -> c[!d];
45         null -> c[d] -> c[!d] = root -> rz();
46         root = t;
47     }
48
49     void finish(int d)
50     {
51         node *t = null -> c[d], *p = root -> c[!d];
52         while (t != null)
53         {
54             t = null -> c[d] -> c[d];
55             null -> c[d]  -> c[d] = p;
56             p = null -> c[d] -> rz();
57             null -> c[d] = t;
58         }
59         root -> c[!d] = p;
60     }
61     void select(int k)//谁有k个儿子
62     {
63         int t;
64         while (1)
65         {
66             bool d = k > (t = root -> c[0] -> size);
67             if (k == t || root -> c[d] == null)    break;
68             if (d)    k -= t + 1;
69             bool dd = k > (t = root -> c[d] -> c[0] -> size);
70             if (k == t || root -> c[d] -> c[dd] == null){zig(d); break;}
71             if (dd) k -= t + 1;
72             d != dd ? zig(d), zig(dd) : zigzig(d);
73         }
74         finish(0), finish(1);
75         root -> rz();
76     }
77     void search(int x)
78     {
79         while (1)
80         {
81             bool d = x > root -> key;
82             if (root -> c[d] == null)    break;
83             bool dd = x > root -> c[d] -> key;
84             if (root -> c[d] -> c[dd] == null){zig(d); break;}
85             d != dd ? zig(d), zig(dd) : zigzig(dd);
86         }
87         finish(0), finish(1);
88         root -> rz();
89         if (x > root -> key)    select(root -> c[0] -> size + 1);
90     }
91
92     void ins(int x)
93     {
94         search(x);
95         node *oldroot = root;
96         root = new node(x, oldroot -> c[0],oldroot);
97         oldroot -> c[0] = null;
98         oldroot -> rz();
99         root -> rz();
100     }
101     int sel(int k){return select(k - 1), root -> key;}
102     int ran(int x){return search(x), root -> c[0] -> size + 1;}
103 }*sp;
104
105
106 int main()
107 {
108     int tt;
109     scanf("%d", &tt);
110     for (int i = 1; i <= tt; ++ i)
111     {
112         sp = new splay;
113         cout<<"Scenario #"<<i<<":"<<endl;
114         scanf("%d", &n);
115         int ans = 0;
116         int tmp;
117         for (int i = 0; i != n; ++ i)
118         {
119             scanf("%d", &tmp);
120             tmp = - tmp;
121             ans +=     sp -> ran(tmp) - 1;
122             //cout<<sp.ran(tmp) - 1<<endl;
123             sp -> ins(tmp);
124         }
125         delete sp;
126         cout<<ans<<endl<<endl;
127     }
128 }

## 线段树 --- (单点更新、求区间最值、模板题)

A - 敌兵布阵 Time Limit:1000MS     Memory Limit:32768KB     64bit IO Format:%I64d & %I64u Description C国的死对头A国这段时间正在进行军事演习,所以C国间谍头子Derek和他手下Tidy又开始忙乎了.A国在海岸线沿直线布置了N个工兵营 地,Derek和Tidy的任务就是要监视这些工兵营地的活动情况.由于采取了某种先进的监测手段,所以每个工兵营地的人数C国都掌握的一清二楚,每个工 兵营地的人数都有可能发生

## POJ 3264 Balanced Lineup (线段树单点更新 区间查询)

Balanced Lineup Time Limit: 5000MS   Memory Limit: 65536K Total Submissions: 36820   Accepted: 17244 Case Time Limit: 2000MS Description For the daily milking, Farmer John's N cows (1 ≤ N ≤ 50,000) always line up in the same order. One day Farmer Joh