//POJ 2299 && ZOJ 2386 Ultra-QuickSort 线段树
/*
题意:
给一个序列,序列中的数都不重复,每次可以将序列中的两个数交换,
求将这个序列变成升序序列的最小交换次数
思路:
其实就是求这个序列的逆序数,离散化后边查询边插入即可
注意ans会爆int
*/
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define lson rt<<1,l,mid
#define rson rt<<1|1,mid+1,r
#define N 500005
int sum[N<<2],a[N],b[N];
int n,cnt;
__int64 ans;
int cmp(const void *a,const void *b){
return *(int *)a -*(int *)b;
}
int Bin(int key){
int l = 1,r = cnt,mid;
while(r >= l){
mid = (l + r) >> 1;
if(b[mid] == key) return mid;
if(b[mid] < key) l = mid + 1;
else r = mid-1;
}
return -1;
}
void Build(){
memset(sum,0,sizeof(sum));
}
void Pushup(int rt){
sum[rt] = sum[rt<<1] + sum[rt<<1|1];
}
void Update(int rt,int l,int r,int x){
if(l == r){
++sum[rt];
return;
}
int mid = (l + r) >> 1;
if(x <= mid) Update(lson,x);
else Update(rson,x);
Pushup(rt);
}
int Query(int rt,int l,int r,int L,int R){
if(L <= l && R >= r){
return sum[rt];
}
int mid = (l + r) >> 1;
int res = 0;
if(L <= mid) res += Query(lson,L,R);
if(R > mid ) res += Query(rson,L,R);
return res;
}
int main(){
int i;
while(scanf("%d",&n),n){
for(i = 1; i <= n; ++i){
scanf("%d",&b[i]);
a[i] = b[i];
}
qsort(b+1,n,sizeof(b[0]),cmp);
cnt = n;
Build();
ans = 0;
for(i = 1; i <= n; ++i){
int x = Bin(a[i]);
ans += Query(1,1,cnt,x,cnt);
Update(1,1,cnt,x);
}
printf("%I64d\n",ans);
}
return 0;
}
分享到:
相关推荐
北大POJ2299-Ultra-QuickSort 解题报告+AC代码
POJ_TL 白话字(POJ) vs. 台罗(TL) 转换家私Python3 模组作者:潘科元版本:0.0.6-20150820授权:GNU General Public License, version 3.0 (GPL-3.0) pojt_pojs() pojs_tls() tls_tlt()POJ調號式--------------->...
在这里要用到__int64,也就是long long int
POJ水题集-----50道左右-----增加自信啊..
北大POJ3292-Semi-prime H-numbers 解题报告+AC代码
非常全的poj答案库 1164-1874 1000-4007
POJ2528-Mayor's posters 【区间映射压缩(离散化)+线段树】 解题报告+AC代码 http://hi.csdn.net/!s/83XZJU ========> 我的所有POJ解题报告链接: http://blog.csdn.net/lyy289065406/article/details/6642573
自动探测POJ、HDU、SOJ、ZOJ水题,对于有志于刷遍各种水题的ACMer来说非常有用
学习ACM程序设计的朋友一定要看,这是训练必备的POJ ZOJ题目分类及解题思路
这是一道很不错的题目,即可以用线段树做也可以用树状数组,可谓经典。不过当然了线段树是比较难搞,而树状数组是极其简洁的,构造很简单,下面就分别来介绍一下两种方法...
问题:求平面上多个矩形的总面积。 算法:线段树(经典的线段树题目)
北大POJ2002-Squares 解题报告+AC代码
NULL 博文链接:https://128kj.iteye.com/blog/1740501
poj2823,使用线段树进行查询区域间最大最小值,线段树初步
Interview,ZOJ,POJ 等平台。 欢迎Coders对代码加以指正和提议! 常见问题总结 两整数求平均值 average = min + (max - min) / 2 防止两整数的和越界 整数乘积对比 1.0 * m * m == num 类似乘积对比, 需转为double...
北大POJ3253-POJ3253-Fence Repair【STL优先队列】 解题报告+AC代码
北大POJ2305-Basic remains POJ2305-Basic remains
POJ3352-Road Construction 【Tarjan-边双连通分量-缩点】 解题报告+AC代码 http://hi.csdn.net/!s/0T8UO5 附:我所有的POJ解题报告链接 . http://blog.csdn.net/lyy289065406/article/details/6642573
POJ3177-Redundant Paths 【Tarjan-边双连通分量-缩点】 解题报告+AC代码+测试数据 http://hi.csdn.net/!s/GPAY6Z 附:我所有的POJ解题报告链接 . http://blog.csdn.net/lyy289065406/article/details/6642573
北大POJ1321-Chess Problem POJ1321-Chess Problem