husj oj
2360 단어 ACM-데이터 구조선분 트 리 & & 트 리 배열
Time Limit:500MS Memory Limit:4096KB 64bit IO Format:%I64d & %I64u
Submit
Status
Description
There are N integers (1<=N<=65537) A1, A2,.. AN (0<=Ai<=10^9). You need to find amount of such pairs (i, j) that 1<=iA[j].
Input
The first line of the input contains the number N. The second line contains N numbers A1...AN.
Output
Write amount of such pairs.
Sample Input
Input
5 2 3 1 5 4
Output
3
仍然是逆序数。不知道哪个oj上的
要用__int64,不能用long long
离散化的时候要注意相同的值
还有注意从后往前插,查询比其小的数字的个数
不需要多组数据。(tle n次)
代码如下:
#include
#include
#include
#include
using namespace std;
const int maxn=65540;
int a[maxn];
int c[maxn];
struct Item
{
int val;
int pos;
}item[maxn];
bool cmp(Item a,Item b)
{
return a.val0;i-=Lowbit(i))
ans+=a[i];
return ans;
}
int main()
{
__int64 ans=0;
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&item[i].val);
item[i].pos=i;
}
sort(item+1,item+n+1,cmp);
c[item[1].pos]=1;
for(int i=2;i<=n;i++){
if(item[i].val!=item[i-1].val)
c[item[i].pos]=i;
else
c[item[i].pos]=c[item[i-1].pos];
}
for(int i=n;i>=1;i--){
update(c[i],1);
ans+=query(c[i]-1);
}
printf("%I64d
",ans);
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
HDU 6325 Interstellar Travel [돌출]제목 링크 After trying hard for many years, Little Q has finally received an astronaut license. Little Q knows the position ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.