POJ.2299 Ultra-QuickSort (线段树 单点更新 区间求和 逆序对 离散化)
题意分析
前置技能
线段树求逆序对
离散化
- 线段树求逆序对已经说过了,具体方法请看这里
- 离散化
有些数据本身很大,自身无法作为数组的下标保存对应的属性。
如果这时只是需要这堆数据的相对属性, 那么可以对其进行离散化处理!
当数据只与它们之间的相对大小有关,而与具体是多少无关时,可以进行离散化。例如:
9 1 0 5 4 与 5 2 1 4 3 的逆序对个数相同。
设有4个数:
1234567、123456789、12345678、123456
排序:123456<1234567<12345678<123456789
=> 1 < 2 < 3 < 4
那么这4个数可以表示成:2、4、3、1
需要注意就是ans会爆int,long long 比较稳
#include <cstdio>
#include <algorithm>
#include <cstring>
#define maxn 500105
#define ls l,m,rt<<1
#define rs m+1,r,rt<<1|1
#define ll long long
using namespace std;
int Sum[maxn<<2];
struct temp{
int v;
int pos;
}x[maxn];
int N;
bool cmp(temp a ,temp b)
{
if(a.v<b.v) return true;
else return false;
}
bool cmp2(temp a, temp b)
{
return a.pos < b.pos;
}
void PushUp (int rt){
Sum[rt]=Sum[rt<<1]+Sum[rt<<1|1];
}
void Build(int l,int r,int rt){
if(l==r) {
Sum[rt] = 0;
return;
}
int m=(l+r)>>1;
Build(l,m,rt<<1);
Build(m+1,r,rt<<1|1);
PushUp(rt);
}
void UpdatePoint(int L,int l,int r,int rt){
if(l==r){
Sum[rt]++;
return;
}
int m=(l+r)>>1;
if(L <= m) UpdatePoint(L,l,m,rt<<1);
else UpdatePoint(L,m+1,r,rt<<1|1);
PushUp(rt);
}
int Query(int L,int R,int l,int r,int rt){
if(L <= l && r <= R){
return Sum[rt];
}
int m = (l+r)>>1;
int ANS = 0;
if(L <= m) ANS += Query(L,R,l,m,rt<<1);
if(R > m) ANS += Query(L,R,m+1,r,rt<<1|1);
return ANS;
}
int main()
{
//freopen("in.txt","r",stdin);
while(scanf("%d",&N)!=EOF && N){
ll sum = 0;
memset(Sum,0,sizeof Sum);
memset(x,0,sizeof x);
Build(1,maxn,1);
for(int i = 0;i<N;++i){
scanf("%d",&x[i].v);
x[i].pos = i+1;
}
sort(x,x+N,cmp);
for(int i = 0;i<N;++i) x[i].v = i+1;
sort(x,x+N,cmp2);
for(int i = 0;i<N;++i){
sum += Query(x[i].v+1,maxn,1,maxn,1);
UpdatePoint(x[i].v,1,maxn,1);
}
printf("%I64d\n",sum);
}
return 0;
}
POJ.2299 Ultra-QuickSort (线段树 单点更新 区间求和 逆序对 离散化)的更多相关文章
-
HDU.1394 Minimum Inversion Number (线段树 单点更新 区间求和 逆序对)
HDU.1394 Minimum Inversion Number (线段树 单点更新 区间求和 逆序对) 题意分析 给出n个数的序列,a1,a2,a3--an,ai∈[0,n-1],求环序列中逆序对 ...
-
POJ.3321 Apple Tree ( DFS序 线段树 单点更新 区间求和)
POJ.3321 Apple Tree ( DFS序 线段树 单点更新 区间求和) 题意分析 卡卡屋前有一株苹果树,每年秋天,树上长了许多苹果.卡卡很喜欢苹果.树上有N个节点,卡卡给他们编号1到N,根 ...
-
hdu 1166线段树 单点更新 区间求和
敌兵布阵 Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)Total Submis ...
-
hdu1166(线段树单点更新&;区间求和模板)
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1166 题意:中文题诶- 思路:线段树单点更新,区间求和模板 代码: #include <iost ...
-
hdu1394(枚举/树状数组/线段树单点更新&;区间求和)
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1394 题意:给出一个循环数组,求其逆序对最少为多少: 思路:对于逆序对: 交换两个相邻数,逆序数 +1 ...
-
poj 2892---Tunnel Warfare(线段树单点更新、区间合并)
题目链接 Description During the War of Resistance Against Japan, tunnel warfare was carried out extensiv ...
-
hdu2795(线段树单点更新&;区间最值)
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=2795 题意:有一个 h * w 的板子,要在上面贴 n 条 1 * x 的广告,在贴第 i 条广告时要 ...
-
POJ 2892 Tunnel Warfare(线段树单点更新区间合并)
Tunnel Warfare Time Limit: 1000MS Memory Limit: 131072K Total Submissions: 7876 Accepted: 3259 D ...
-
HDU 3308 LCIS(线段树单点更新区间合并)
LCIS Given n integers. You have two operations: U A B: replace the Ath number by B. (index counting ...
随机推荐
-
java大数总结【转】
java大数(2013长春网络赛)--hdu4762总结一下:1.java提交类要写Main.2.读取大数. Scanner read=new Scanner(System.in); BigInteg ...
-
mysql_config not found
在python中安装MySQL_python.不想通过下载源码编译,而是想用 easy_install MySQL_python 来安装.结果一直报错: mysql_config not found ...
-
CommonsChunkPlugin并不是分离第三方库的好办法(DllPlugin科学利用浏览器缓存)
webpack算是个磨人的小妖精了.之前一直站在glup阵营,使用browserify打包,发现webpack已经火到爆炸,深怕被社区遗落,赶紧拿起来把玩一下.本来只想玩一下的.尝试打包了以后,就想启 ...
-
【转】10分钟就能学会的.NET Core配置
.NET Core为我们提供了一套用于配置的API,它为程序提供了运行时从文件.命令行参数.环境变量等读取配置的方法.配置都是键值对的形式,并且支持嵌套,.NET Core还内建了从配置反序列化为PO ...
-
H5 id选择器和class选择器
11-id选择器和class选择器 第一段文字 第二段文字 第三段文字 --> 第一段文字 第二段文字 第三段文字 <!DOCTYPE html> <html lang=&qu ...
-
uip移植telnetd并加入自己定义命令
版权声明: https://blog.csdn.net/cp1300/article/details/30541507 刚刚移植了一下uip的telnetd,还是比較简单方便的. 首先加入文件,注意u ...
-
iOS开发手记-仿QQ音乐播放器动态歌词的实现
最近朋友想做个音乐App,让我帮忙参考下.其中歌词动态滚动的效果,正好我之前也没做过,顺便学习一下,先来个预览效果. 实现思路 歌词常见的就是lrc歌词了,我们这里也是通过解析lrc歌词文件来获取其播 ...
-
添加图片后xcode报错:resource fork, Finder information, or similar detritus not allowed
/Users/songximing/Library/Developer/Xcode/DerivedData/Children-cvqgzlzddltkfndhdmzedxbnoxwx/Build/Pr ...
-
::selection 选择器
使被选中的文本成为红色:::selection { color:#ff0000; } ::-moz-selection { color:#ff0000; }
-
【转】【delphi】ClientDataSet详细解读
原文:http://www.cnblogs.com/lcw/p/3496764.html TClientDataSet的基本属性和方法 TClientDataSet控件继承自TDataSet,其数据存 ...