1 条题解
-
0
使用 long long 累加逆序数,覆盖 n=100000 的逆序上界。
#include <bits/stdc++.h> using namespace std; int main(){int n;cin>>n;vector<int>bit(n+1);long long count=0;for(int i=0;i<n;i++){int x;cin>>x;int small=0;for(int j=x;j;j-=j&-j)small+=bit[j];count+=i-small;for(int j=x;j<=n;j+=j&-j)bit[j]++;}cout<<count<<"\n";}
- 1
信息
- ID
- 3912
- 时间
- 1000ms
- 内存
- 128MiB
- 难度
- 4
- 标签
- 递交数
- 0
- 已通过
- 0
- 上传者