POJ.2299 Ultra-QuickSort (线段树 单点更新 区间求和 逆序对 离散化)

时间:2021-07-29 17:01:41

POJ.2299 Ultra-QuickSort (线段树 单点更新 区间求和 逆序对 离散化)

题意分析

前置技能

线段树求逆序对

离散化

  1. 线段树求逆序对已经说过了,具体方法请看这里
  2. 离散化

    有些数据本身很大,自身无法作为数组的下标保存对应的属性。

    如果这时只是需要这堆数据的相对属性, 那么可以对其进行离散化处理!

    当数据只与它们之间的相对大小有关,而与具体是多少无关时,可以进行离散化。例如:

    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 (线段树 单点更新 区间求和 逆序对 离散化)的更多相关文章

  1. HDU&period;1394 Minimum Inversion Number &lpar;线段树 单点更新 区间求和 逆序对&rpar;

    HDU.1394 Minimum Inversion Number (线段树 单点更新 区间求和 逆序对) 题意分析 给出n个数的序列,a1,a2,a3--an,ai∈[0,n-1],求环序列中逆序对 ...

  2. POJ&period;3321 Apple Tree &lpar; DFS序 线段树 单点更新 区间求和&rpar;

    POJ.3321 Apple Tree ( DFS序 线段树 单点更新 区间求和) 题意分析 卡卡屋前有一株苹果树,每年秋天,树上长了许多苹果.卡卡很喜欢苹果.树上有N个节点,卡卡给他们编号1到N,根 ...

  3. hdu 1166线段树 单点更新 区间求和

    敌兵布阵 Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)Total Submis ...

  4. hdu1166&lpar;线段树单点更新&amp&semi;区间求和模板&rpar;

    题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1166 题意:中文题诶- 思路:线段树单点更新,区间求和模板 代码: #include <iost ...

  5. hdu1394&lpar;枚举&sol;树状数组&sol;线段树单点更新&amp&semi;区间求和&rpar;

    题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1394 题意:给出一个循环数组,求其逆序对最少为多少: 思路:对于逆序对: 交换两个相邻数,逆序数 +1 ...

  6. poj 2892---Tunnel Warfare(线段树单点更新、区间合并)

    题目链接 Description During the War of Resistance Against Japan, tunnel warfare was carried out extensiv ...

  7. hdu2795&lpar;线段树单点更新&amp&semi;区间最值&rpar;

    题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=2795 题意:有一个 h * w 的板子,要在上面贴 n 条 1 * x 的广告,在贴第 i 条广告时要 ...

  8. POJ 2892 Tunnel Warfare(线段树单点更新区间合并)

    Tunnel Warfare Time Limit: 1000MS   Memory Limit: 131072K Total Submissions: 7876   Accepted: 3259 D ...

  9. HDU 3308 LCIS&lpar;线段树单点更新区间合并)

    LCIS Given n integers. You have two operations: U A B: replace the Ath number by B. (index counting ...

随机推荐

  1. java大数总结【转】

    java大数(2013长春网络赛)--hdu4762总结一下:1.java提交类要写Main.2.读取大数. Scanner read=new Scanner(System.in); BigInteg ...

  2. mysql&lowbar;config not found

    在python中安装MySQL_python.不想通过下载源码编译,而是想用 easy_install MySQL_python 来安装.结果一直报错: mysql_config not found ...

  3. CommonsChunkPlugin并不是分离第三方库的好办法(DllPlugin科学利用浏览器缓存)

    webpack算是个磨人的小妖精了.之前一直站在glup阵营,使用browserify打包,发现webpack已经火到爆炸,深怕被社区遗落,赶紧拿起来把玩一下.本来只想玩一下的.尝试打包了以后,就想启 ...

  4. 【转】10分钟就能学会的&period;NET Core配置

    .NET Core为我们提供了一套用于配置的API,它为程序提供了运行时从文件.命令行参数.环境变量等读取配置的方法.配置都是键值对的形式,并且支持嵌套,.NET Core还内建了从配置反序列化为PO ...

  5. H5 id选择器和class选择器

    11-id选择器和class选择器 第一段文字 第二段文字 第三段文字 --> 第一段文字 第二段文字 第三段文字 <!DOCTYPE html> <html lang=&qu ...

  6. uip移植telnetd并加入自己定义命令

    版权声明: https://blog.csdn.net/cp1300/article/details/30541507 刚刚移植了一下uip的telnetd,还是比較简单方便的. 首先加入文件,注意u ...

  7. iOS开发手记-仿QQ音乐播放器动态歌词的实现

    最近朋友想做个音乐App,让我帮忙参考下.其中歌词动态滚动的效果,正好我之前也没做过,顺便学习一下,先来个预览效果. 实现思路 歌词常见的就是lrc歌词了,我们这里也是通过解析lrc歌词文件来获取其播 ...

  8. 添加图片后xcode报错:resource fork&comma; Finder information&comma; or similar detritus not allowed

    /Users/songximing/Library/Developer/Xcode/DerivedData/Children-cvqgzlzddltkfndhdmzedxbnoxwx/Build/Pr ...

  9. &colon;&colon;selection 选择器

    使被选中的文本成为红色:::selection { color:#ff0000; } ::-moz-selection { color:#ff0000; }

  10. 【转】【delphi】ClientDataSet详细解读

    原文:http://www.cnblogs.com/lcw/p/3496764.html TClientDataSet的基本属性和方法 TClientDataSet控件继承自TDataSet,其数据存 ...