学步园

使用线段树优化使得求初始数列的逆序数的时间复杂度从O(n ^ 2) 降到 O(n log(n))

/*<br /> Author: ACb0y<br /> Date: 2010年11月16日14:59:06<br /> Type: math<br /> ProblemId: hdu 1394 Minimum Inversion Number<br /> Result: 3201273 2010-11-16 14:55:27 Accepted 1394 62MS 380K 1741 B G++ ACb0y<br /> 备注：本题使用了线段树进行优化。速度提高了4倍左右，时间复杂度从n^2 降到nlog(n)<br /> */</p> <p>#include <iostream><br /> using namespace std;</p> <p>struct node {<br /> int left;<br /> int right;<br /> int cnt;<br /> };</p> <p>int data[5005];<br /> node seg_tree[5005 * 3];</p> <p>void create_tree(int left, int right, int loc) {<br /> seg_tree[loc].left = left;<br /> seg_tree[loc].right = right;<br /> seg_tree[loc].cnt = 0;<br /> if (right == left) {<br /> return;<br /> }<br /> int mid = (left + right) / 2;<br /> create_tree(left, mid, loc << 1);<br /> create_tree(mid + 1, right, (loc << 1) + 1);<br /> }</p> <p>void update_tree(int value, int loc) {<br /> seg_tree[loc].cnt++;<br /> if (seg_tree[loc].right == seg_tree[loc].left && seg_tree[loc].right == value) {<br /> seg_tree[loc].cnt = 1;<br /> return;<br /> }<br /> int mid = (seg_tree[loc].right + seg_tree[loc].left) / 2;<br /> if (value <= mid) {<br /> update_tree(value, loc << 1);<br /> } else {<br /> update_tree(value, (loc << 1) + 1);<br /> }<br /> }</p> <p>int query_tree(int left, int right, int loc) {<br /> if (seg_tree[loc].left == left && seg_tree[loc].right == right) {<br /> return seg_tree[loc].cnt;<br /> }<br /> int mid = (seg_tree[loc].right + seg_tree[loc].left) >> 1;<br /> if (right <= mid) {<br /> return query_tree(left, right, loc << 1);<br /> } else if (mid < left) {<br /> return query_tree(left, right, (loc << 1) + 1);<br /> } else {<br /> return query_tree(left, mid, loc << 1) + query_tree(mid + 1, right, (loc << 1) + 1);<br /> }<br /> }</p> <p>int main()<br /> {<br /> int n;<br /> int i, j;<br /> #ifndef ONLINE_JUDGE<br /> freopen("in.txt", "r", stdin);<br /> #endif<br /> while (scanf("%d", &n) != EOF) {<br /> for (i = 0; i < n; ++i) {<br /> scanf("%d", &data[i]);<br /> }<br /> create_tree(1, n, 1);<br /> int min = 0;<br /> for (i = 0; i < n; ++i) {<br /> min += query_tree(data[i] + 1, n, 1);<br /> update_tree(data[i], 1);<br /> }</p> <p> int temp = min;<br /> for (i = 0; i < n - 1; ++i) {<br /> temp = temp - data[i] + (n - data[i] - 1);<br /> if (temp < min) {<br /> min = temp;<br /> }<br /> }<br /> cout << min << endl;<br /> }<br /> return 0;<br /> }<br />