为什么线段树能够求逆序数?
首先要求一个逆序数有两种方式:能够从头開始往后找比当前元素小的值,也能够从后往前找比当前元素大的值,有几个逆序数就是几。
线段树就是应用从后往前找较大值得个数。(一边更新一边查)
当前个数是 n = 10
元素 9 5 3
9先增加线段树,T【9】+=1;查从T【9】到T【10】比9大的值,没有sum = 0。
5 增加线段树。T【5】 += 1。查从T【5】到T【10】比5大的值。有一个9。sum +=1;
3 增加线段树,T【3】 += 1,查从T【3】到T【10】比3大的值,有两个9和5,sum +=2;
终于sum = 3;
若元素值不能确定。那么首先讲数列离散化,在从前往后枚举。找后面比前面小的统计个数……
离散化:比如2 5 8 3 10 等价于 1 3 4 2 5,能够通过排序加小小处理解决。
比如:
元素 9 5 3 4 1 离散化后得到索引
索引 1 2 3 4 5
将元素升序排序
元素 1 3 4 5 9
索引 5 3 4 2 1
枚举到第i个数,我们须要求出从1到i-1中有多少个比a[i]大的数,更新答案。
详细怎么做呢?
每次枚举完一个数之后。将这个数插入到线段树里(注意:插到与其相应的位置)。
举个样例:3 2 4 1。
则线段树的变化应该为:t[3]+=1;t[2]+=1;t[4]+=1;t[1]+=1;
设x=a[i],这样,在插入一个数X时,首先求一下t[x+1]~t[n]的和,这个和就是1~i-1中有多少个比a[i]大的数
由于求一个数列的逆序数能够从两个
在你插a[i]时,前面已经有多少个比a[i]大的数
POJ 2299 #include <iostream> #include <cstdio> #include <cstdlib> #include <cstring> #include <algorithm> #include <cmath> using namespace std; #define MAX INT_MAX #define MIN INT_MIN #define LL __int64 #define init(a) memset(a,0,sizeof(a)) #define lson l , m , rt << 1 #define rson m + 1 , r , rt << 1 | 1 const int maxn = 500010; using namespace std; int T[maxn<<2], index[maxn], num[maxn]; int n; int cmp(const int i, const int j) { return num[i] < num[j]; } void update( int l, int r,int rt, int num, int add) { T[rt] += add; if(r==l) return ; int m = (l+r) >> 1; if(num <= m) update(lson, num, add); else update(rson, num, add); } int query( int l, int r, int rt,int L, int R) { if(L<=l && r<=R) return T[rt]; int m = (l+r) >> 1; int ans = 0; if(L <= m) ans += query(lson, L, R); if(R > m) ans += query(rson, L, R); return ans; } int main() { while(~scanf("%d", &n)) { if(n==0) break; init(index); for(int i=1;i<=n;i++) { scanf("%d", &num[i]); update(1, n,1, i, 1);//离散化 index[i] = i; } sort(index+1, index+n+1,cmp); //排序num。更新索引 LL sum = 0; for(int i=1;i<=n;i++) { sum += (query( 1, n,1, 1, index[i])-1); update(1, n,1, index[i], -1); } printf("%I64d ", sum); } return 0; }
HDU 1394
题意:一组数 每次把最前面的元素放在最后生成新的序列。再统计逆序数,求全部逆序中最小值
有一个公式:先求出原数列的逆序数。sum
那么每次新逆序数 = sum-a[i] + (n-a[i] - 1)
#include <iostream> #include <cstdio> #include <cstdlib> #include <cstring> #include <algorithm> #include <cmath> using namespace std; #define MAX INT_MAX #define MIN INT_MIN #define LL __int64 #define init(a) memset(a,0,sizeof(a)) #define lson l , m , rt << 1 #define rson m + 1 , r , rt << 1 | 1 const int maxn = 500010; using namespace std; int T[maxn<<2], index[maxn], num[maxn]; int n; int cmp(const int i, const int j) { return num[i] < num[j]; } void update( int l, int r,int rt, int num, int add) { T[rt] += add; if(r==l) return ; int m = (l+r) >> 1; if(num <= m) update(lson, num, add); else update(rson, num, add); } int query( int l, int r, int rt,int L, int R) { if(L<=l && r<=R) return T[rt]; int m = (l+r) >> 1; int ans = 0; if(L <= m) ans += query(lson, L, R); if(R > m) ans += query(rson, L, R); return ans; } int main() { while(~scanf("%d", &n)) { if(n==0) break; init(index); for(int i=1;i<=n;i++) { scanf("%d", &num[i]); update(1, n,1, i, 1); index[i] = i; } sort(index+1, index+n+1,cmp); LL sum = 0; for(int i=1;i<=n;i++) { sum += (query( 1, n,1, 1, index[i])-1); update(1, n,1, index[i], -1); } // printf("%I64d ", sum); LL ans = sum; for(int i = 1;i<=n;i++) { sum = sum - num[i] + (n-num[i]- 1); ans = min(sum,ans); } cout<<ans<<endl; } return 0; }