http://acm.nyist.net/JudgeOnline/problem.php?pid=117树状数组求逆序数+离散化

本文主要是介绍http://acm.nyist.net/JudgeOnline/problem.php?pid=117树状数组求逆序数+离散化,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

这一题一开始是胸有成竹的,本想1A的,但是接二连三的wa了好几次。。。把我满满的自信心消磨殆尽了。。我一遍一遍的寻找错误,就是找不到。。最后实在没办法要了后台的数据。。运行一看。令我大跌眼眶。。。。竟然都对了,,但为什么WA呢?可能是这一题判题写错了?,最后在不抱希望的情况下我把%I64d改成了%lld,竟然AC了,苦逼的孩子。。oj竟然不支持%I64d.....

AC代码:

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<string.h>
#define N 1000005
using namespace std;
int s[N];
int kp[N];
int  a[N];
int tot;
typedef long long L;
int lowbit(int x)
{return x&(-x);
}
void update(int x)
{while(x<N){   s[x]++;x+=lowbit(x);}
}
L Quary(int x)
{ L sum=0;while(x>0){ sum+=s[x];x-=lowbit(x);}return sum;
}
int lisan(int x)
{  int l=1,r=tot;while(l<=r){  int mid=(l+r)>>1;if(a[mid]==x) return mid;else if(a[mid]<x)  l=mid+1;else if(a[mid]>x)  r=mid-1;}
}
int main()
{ int T;//freopen("d:\\1.txt","r",stdin);//freopen("d:\\2.txt","w",stdout);scanf("%d",&T);while(T--){  memset(s,0,sizeof(s));int n;scanf("%d",&n);tot=0;for(int i=1;i<=n;++i){scanf("%d",&kp[i]);a[i]=kp[i];}sort(a+1,a+n+1);for(int i=1;i<=n;++i)if(i==1||a[i]!=a[i-1])a[++tot]=a[i];L res=0;for(int i=1;i<=n;++i){  int num=lisan(kp[i]);update(num);res+=i-Quary(num);}printf("%lld\n",res);}return 0;
}



这篇关于http://acm.nyist.net/JudgeOnline/problem.php?pid=117树状数组求逆序数+离散化的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/590070

相关文章

MySQL查询JSON数组字段包含特定字符串的方法

《MySQL查询JSON数组字段包含特定字符串的方法》在MySQL数据库中,当某个字段存储的是JSON数组,需要查询数组中包含特定字符串的记录时传统的LIKE语句无法直接使用,下面小编就为大家介绍两种... 目录问题背景解决方案对比1. 精确匹配方案(推荐)2. 模糊匹配方案参数化查询示例使用场景建议性能优

关于集合与数组转换实现方法

《关于集合与数组转换实现方法》:本文主要介绍关于集合与数组转换实现方法,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录1、Arrays.asList()1.1、方法作用1.2、内部实现1.3、修改元素的影响1.4、注意事项2、list.toArray()2.1、方

springboot如何通过http动态操作xxl-job任务

《springboot如何通过http动态操作xxl-job任务》:本文主要介绍springboot如何通过http动态操作xxl-job任务的问题,具有很好的参考价值,希望对大家有所帮助,如有错... 目录springboot通过http动态操作xxl-job任务一、maven依赖二、配置文件三、xxl-

解决未解析的依赖项:‘net.sf.json-lib:json-lib:jar:2.4‘问题

《解决未解析的依赖项:‘net.sf.json-lib:json-lib:jar:2.4‘问题》:本文主要介绍解决未解析的依赖项:‘net.sf.json-lib:json-lib:jar:2.4... 目录未解析的依赖项:‘net.sf.json-lib:json-lib:jar:2.4‘打开pom.XM

javax.net.ssl.SSLHandshakeException:异常原因及解决方案

《javax.net.ssl.SSLHandshakeException:异常原因及解决方案》javax.net.ssl.SSLHandshakeException是一个SSL握手异常,通常在建立SS... 目录报错原因在程序中绕过服务器的安全验证注意点最后多说一句报错原因一般出现这种问题是因为目标服务器

Maven 配置中的 <mirror>绕过 HTTP 阻断机制的方法

《Maven配置中的<mirror>绕过HTTP阻断机制的方法》:本文主要介绍Maven配置中的<mirror>绕过HTTP阻断机制的方法,本文给大家分享问题原因及解决方案,感兴趣的朋友一... 目录一、问题场景:升级 Maven 后构建失败二、解决方案:通过 <mirror> 配置覆盖默认行为1. 配置示

MySQL JSON 查询中的对象与数组技巧及查询示例

《MySQLJSON查询中的对象与数组技巧及查询示例》MySQL中JSON对象和JSON数组查询的详细介绍及带有WHERE条件的查询示例,本文给大家介绍的非常详细,mysqljson查询示例相关知... 目录jsON 对象查询1. JSON_CONTAINS2. JSON_EXTRACT3. JSON_TA

Linux中修改Apache HTTP Server(httpd)默认端口的完整指南

《Linux中修改ApacheHTTPServer(httpd)默认端口的完整指南》ApacheHTTPServer(简称httpd)是Linux系统中最常用的Web服务器之一,本文将详细介绍如何... 目录一、修改 httpd 默认端口的步骤1. 查找 httpd 配置文件路径2. 编辑配置文件3. 保存

C++ HTTP框架推荐(特点及优势)

《C++HTTP框架推荐(特点及优势)》:本文主要介绍C++HTTP框架推荐的相关资料,本文通过实例代码给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友参考下吧... 目录1. Crow2. Drogon3. Pistache4. cpp-httplib5. Beast (Boos

JAVA数组中五种常见排序方法整理汇总

《JAVA数组中五种常见排序方法整理汇总》本文给大家分享五种常用的Java数组排序方法整理,每种方法结合示例代码给大家介绍的非常详细,感兴趣的朋友跟随小编一起看看吧... 目录前言:法一:Arrays.sort()法二:冒泡排序法三:选择排序法四:反转排序法五:直接插入排序前言:几种常用的Java数组排序