首页 > 代码库 > POJ训练计划2299_Ultra-QuickSort(线段树/单点更新)
POJ训练计划2299_Ultra-QuickSort(线段树/单点更新)
解题报告
题意:
求逆序数。
思路:
线段树离散化处理。
#include <algorithm> #include <iostream> #include <cstring> #include <cstdio> #define LL long long using namespace std; LL sum[2001000],num[501000],_hash[501000]; void push_up(int rt) { sum[rt]=sum[rt*2]+sum[rt*2+1]; } void update(int rt,int l,int r,int p,LL v) { if(l==r) { sum[rt]=+v; return; } int mid=(l+r)/2; if(p<=mid)update(rt*2,l,mid,p,v); else update(rt*2+1,mid+1,r,p,v); push_up(rt); } LL q_sum(int rt,int l,int r,int ql,int qr) { if(ql>r||qr<l)return 0; if(ql<=l&&r<=qr)return sum[rt]; int mid=(l+r)/2; return q_sum(rt*2,l,mid,ql,qr)+q_sum(rt*2+1,mid+1,r,ql,qr); } int main() { int n,i,j; while(~scanf("%d",&n)) { LL ans=0; if(!n)break; memset(_hash,0,sizeof(_hash)); memset(num,0,sizeof(num)); memset(sum,0,sizeof(sum)); for(i=0; i<n; i++) { scanf("%LLd",&num[i]); _hash[i]=num[i]; } sort(_hash,_hash+n); int m=unique(_hash,_hash+n)-_hash; for(i=0; i<n; i++) { int t=lower_bound(_hash,_hash+m,num[i])-_hash+1; ans+=q_sum(1,1,m,t+1,m); update(1,1,m,t,1); } printf("%lld\n",ans); } return 0; }
Ultra-QuickSort
Time Limit: 7000MS | Memory Limit: 65536K | |
Total Submissions: 41278 | Accepted: 14952 |
Description
In this problem, you have to analyze a particular sorting algorithm. The algorithm processes a sequence of n distinct integers by swapping two adjacent sequence elements until the sequence is sorted in ascending order. For the input sequence
9 1 0 5 4 ,
Ultra-QuickSort produces the output
0 1 4 5 9 .
Your task is to determine how many swap operations Ultra-QuickSort needs to perform in order to sort a given input sequence.
Ultra-QuickSort produces the output
Your task is to determine how many swap operations Ultra-QuickSort needs to perform in order to sort a given input sequence.
Input
The input contains several test cases. Every test case begins with a line that contains a single integer n < 500,000 -- the length of the input sequence. Each of the the following n lines contains a single integer 0 ≤ a[i] ≤ 999,999,999, the i-th input sequence element. Input is terminated by a sequence of length n = 0. This sequence must not be processed.
Output
For every input sequence, your program prints a single line containing an integer number op, the minimum number of swap operations necessary to sort the given input sequence.
Sample Input
5 9 1 0 5 4 3 1 2 3 0
Sample Output
6 0
Source
Waterloo local 2005.02.05
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。