网友投稿 891 2022-11-28
POJ 2299 Ultra-QuickSort——离散化+线段树求逆序数
注意求最终结果时用longlong
#include #include #include #include #include using namespace std;const int maxn = 5e5 +10;int n, index[maxn];struct Data { int val, id; bool operator < (const Data &temp) const { return val < temp.val; }}a[maxn];void lisan() { sort(a + 1, a + 1 + n); int cnt = 1; index[a[1].id] = cnt; for (int i = 1; i <= n; i++) { if (a[i].val != a[i - 1].val) ++cnt; index[a[i].id] = cnt; }}struct Tree { int val[maxn<<2]; void init() { memset(val, 0, sizeof(val)); } void pushup(int root) { val[root] = val[root<<1] + val[root<<1|1]; } void updata(int l, int r, int root, int pos) { if (l == r) { val[root] += 1; return; } int mid = (l + r)>>1; if (pos <= mid) updata(l, mid, root<<1, pos); else updata(mid + 1, r, root<<1|1, pos); pushup(root); } int query(int l, int r, int root, int ql, int qr) { if (ql <= l && r <= qr) return val[root]; int mid = (l + r)>>1; int ans = 0; if (ql <= mid) ans += query(l, mid, root<<1, ql, qr); if (mid < qr) ans += query(mid + 1, r, root<<1|1, ql, qr); return ans; }}tree;int main() { while (~scanf("%d", &n) && n) { for (int i = 1; i <= n; i++) { scanf("%d", &a[i].val); a[i].id = i; } lisan(); tree.init(); long long ans = 0; for (int i = n; i >= 1; i--) { if (index[i] - 1 >= 1) ans += tree.query(1, n, 1, 1, index[i] - 1); tree.updata(1, n, 1, index[i]); } printf("%I64d\n", ans); } return 0;}
版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。
发表评论
暂时没有评论，来抢沙发吧~
暂时没有评论，来抢沙发吧~