目录
逆序对简介
逆序对定义
给定一个序列 \(a\)，存在有序对 \((i,j)\)，满足 \(i a_j\)，则称 \((i,j)\) 为一个逆序对。
如何求序列逆序对对数
根据定义：对于一个下标 \(i\)，它能产生的所有逆序对 \((i,j)\)，即为区间 \([i+1,n]\) 中小于 \(a_i\) 的数的个数。
最朴素的 \(O(n^2)\) 做法如下：
[code]for (int i = 1 ; i a; vec.push_back(a); } //离散化 sort(vec.begin(),vec.end()); auto e = unique(vec.begin(),vec.end()); vec.erase(e,vec.end()); siz = vec.size(); ll ans = 0; for (int i = n ; i >= 1 ; i--) { if (!a) continue; ans += query(id(a)-1); insert(id(a)); } cout a; insert(a); ans += query(n) - query(a); } cout 1; if (aim > 1; int sum = 0; if (ql mid) sum += query(pos*2+1,mid+1,r,ql,qr); return sum;}int main(){ ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int n; cin >> n; for (int i = 1 ; i > a; a1 = a; } for (int i = 1 ; i > b; b1 = b; } sort(a1+1,a1+n+1); sort(b1+1,b1+n+1); for (int i = 1 ; i a; vec[i%2].push_back(a); } cnt1 = count(vec[0]); cnt2 = count(vec[1]); sort(vec[0].begin(),vec[0].end()); sort(vec[1].begin(),vec[1].end()); int p[2] = {0}; for (int i = 1 ; i 1; long long sum = 0; if (ql mid) sum += query(pos*2+1,mid+1,r,ql,qr,tr); return sum;}int n;void solve(){ vector a(n+10,vector(n+10)); vector b(n+10,vector(n+10)); for (int i = 1 ; i a[j]; // cout |
提升卡
置顶卡
沉默卡
喧嚣卡
变色卡
千斤顶
照妖镜
