HDU 1394.Minimum Inversion Number-最小逆序数-完全版线段树(单点增减、区间求和)
2024-09-29 16:46:42
HDU1394.Minimum Inversion Number
这个题求最小逆序数,先建一个空的树,然后每输入一个值,就先查询一下,查询之后,更新线段树,然后遍历一遍,每次将第一个数放到最后之后,减少的逆序数为x[i],增加的为n-x[i]-1;
所以该种序列的逆序数为sum+=n-x[i]-x[i]-1。直接遍历的时候找最小值就可以了。
写的脑子有点乱。。。
代码:
//c
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<cstdlib>
#include<queue>
#include<stack>
using namespace std;
typedef long long ll;
const int inf=0x3f3f3f3f;
const double eps=1e-;
const int maxn=*1e5+;
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
int sum[maxn<<],MAX[maxn<<]; void PushUp(int rt){
sum[rt]=sum[rt<<]+sum[rt<<|];
//MAX[rt]=max(MAX[rt<<1],MAX[rt<<1|1]);
}
/*
void build(int l,int r,int rt){
if(l==r){
scanf("%d",&sum[rt]);
//scanf("%d",&MAX[rt]);
return ;
}
int m=(l+r)>>1;
build(lson);
build(rson);
PushUp(rt);
}
*/
void build(int l,int r,int rt){
sum[rt]=;
if(l==r)return ;
int m=(l+r)>>;
build(lson);
build(rson);
}
void update(int p,int l,int r,int rt){
if(l==r){
sum[rt]++;
return ;
}
int m=(l+r)>>;
if(p<=m)update(p,lson);
else update(p,rson);
PushUp(rt);
}
/*
//单点增减
void update(int p,int add,int l,int r,int rt){
if(l==r){
sum[rt]+=add;
return ;
}
int m=(l+r)>>1;
if(p<=m)update(p,add,lson);
else update(p,add,rson);
PushUp(rt);
}
*/
/*
//单点更新
void update(int p,int sc,int l,int r,int rt){
if(l==r){
MAX[rt]=sc;
return ;
}
int m=(l+r)>>1;
if(p<=m)update(p,sc,lson);
else update(p,sc,rson);
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)>>;
int ret=;
if(L<=m)ret+=query(L,R,lson);
if(R>m) ret+=query(L,R,rson);
return ret;
} /*
//区间最值
int query(int L,int R,int l,int r,int rt){
if(L<=l&&r<=R){
return MAX[rt];
}
int m=(l+r)>>1;
int ret=0;
if(L<=m)ret=max(ret,query(L,R,lson));
if(R>m) ret=max(ret,query(L,R,rson));
return ret;
}
*/
int x[maxn];
int main(){
int n;
while(~scanf("%d",&n)){
build(,n-,);
int sum=;
for(int i=;i<n;i++){
scanf("%d",&x[i]);
sum+=query(x[i],n-,,n-,);
update(x[i],,n-,);
}
int ret=sum;
for(int i=;i<n;i++){
sum+=n-x[i]-x[i]-;
ret=min(ret,sum);
}
printf("%d\n",ret);
}
return ;
}
最新文章
- 《一个 Go 程序系统线程暴涨的问题》结论
- gcc与gdb版本兼容问题
- 20160908_Redis主从复制Replication
- const int * p 和 int const * p 和 int * const p 的区别
- Android开发更改应用图标无效的问题
- 同步git修改文件到远端服务器脚本
- 导出Excel offer2007以上
- BZOJ 3997 组合数学
- 【BZOJ1901】 Zju2112 Dynamic Rankings(树套树)
- bzoj1038: [ZJOI2008]瞭望塔
- Java 强引用,软引用,弱引用
- 判断是否联网_检测网络的类型为3G、2G、wap、wifi
- contact表单错误解决记录
- Makefile 使用总结(转)
- function call操作符(operator()) 仿函数(functor)
- Confluence 6 从站点首页集中访问面板
- keil项目的调试与编译
- MongoDB 新建数据库和集合 查询集合
- TortioseSVN切换账号教程
- c++11 noexcept修饰符