网站建设定金合同,公司网站建设会计处理,失效网站建设费支出,电商网销来源#xff1a;牛客网#xff1a;
题目描述
珂朵莉给了你一个序列#xff0c;有n(n1)/2 个子区间#xff0c;求出她们各自的逆序对个数#xff0c;然后加起来输出 输入描述: 第一行一个数 n 表示这个序列 a 的长度
之后一行 n 个数#xff0c;第i个数表示ai
输出…来源牛客网
题目描述
珂朵莉给了你一个序列有n×(n1)/2 个子区间求出她们各自的逆序对个数然后加起来输出 输入描述: 第一行一个数 n 表示这个序列 a 的长度
之后一行 n 个数第i个数表示ai
输出描述: 输出一行一个数表示答案 示例1 输入 复制
10
1 10 8 5 6 2 3 9 4 7输出 复制
270示例2 输入 复制
20
6 0 4 5 8 8 0 6 6 1 0 4 6 6 0 0 7 2 0 5输出 复制
3481备注: 对于100%的数据n 1000000 ,0 序列中每个数 1000000000 题解
如果一个逆序对中两个数的坐标分别是l和r逆序对l,r,我们看有多少区间包含了它 通过组合排列可以得知一共有l*(n-r1)个子区间包含因为子区间肯定要包含[l,r]那左区间范围是1l,长度是右区间是rn长度是n-r1相乘即是 至于逆序对我们可以用树状数组来做 但是本题最难的点来了注意题目范围题目范围贼大即便开longlong也难逃一挂当然你可以用java来做这里介绍一个小技巧 统计答案时我们可以用两个数来存先用第一个数存答案当答案大小出国1e18时我们就将超出部分存到第二个数这里的超出部分是指第1e18位之后的数也就是这两位数拼起来就是答案 这部分对应的代码
ll te1e18
if(ans[0]te)ans[1]ans[0]/te,ans[0]%te;add(a[i],i);if(ans[1])printf(%lld%018lld\n,ans[1],ans[0]);else printf(%lld\n,ans[0]);代码
//求逆序对个数和
#includebits/stdc.h
typedef long long ll;
using namespace std;const int g10.0,eps1e-9;
const int N100000010,maxn500000010,inf0x3f3f3f3f;ll a[N],b[N],sum[N];
int lowbit(int x)
{return x(-x);}
void add(int i,ll x)
{while(iN){sum[i]x;ilowbit(i);}
}
ll query(int i)
{ll ans0;while(i0){anssum[i];i-lowbit(i);}return ans;
}
ll ans[2];
int main()
{/*ios::sync_with_stdio(false);cin.tie(0);*/ll n,cnt0;scanf(%lld,n);for(ll i1;in;i)scanf(%lld,a[i]),b[cnt]a[i];sort(b,bcnt);cntunique(b,bcnt)-b;for(ll i1;in;i)a[i]lower_bound(b,bn,a[i])-b,a[i];//离散化处理 ll te1e18;for(ll i1;in;i){ans[0](ll)(n-i1)*(query(n)-query(a[i]));//逆序对数量 if(ans[0]te)ans[1]ans[0]/te,ans[0]%te;add(a[i],i);}if(ans[1])printf(%lld%018lld\n,ans[1],ans[0]);else printf(%lld\n,ans[0]);return 0;
}
